New measures of graph irregularity

Clive Elphick, Pawel Wocjan


In this paper, we define and compare three new measures of graph irregularity. We use these measures to tighten upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan's theorem can be similarly strengthened for generalized r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised indices of network heterogeneity.



chromatic number, Colin de Verdiere parameter, graph irregularity

Full Text:




  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats