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.
Keywords
chromatic number, Colin de Verdiere parameter, graph irregularity
