Variable neighborhood search for extremal graphs. 23. On the Randić index and the chromatic number

Let G = ( V , E ) be a simple graph with vertex degrees d 1 , d 2 , … , d n . The Randić index R ( G ) is equal to the sum over all edges ( i , j ) ∈ E of weights 1 / d i d j . We prove several conjectures, obtained by the system AutoGraphiX, relating R ( G ) and the chromatic number χ ( G ) . The main result is χ ( G ) ≤ 2 R ( G ) . To prove it, we also show that if v ∈ V is a vertex of minimum degree δ of G , G − v the graph obtained from G by deleting v and all incident edges, and Δ the maximum degree of G , then R ( G ) − R ( G − v ) ≥ 1 2 δ / Δ .