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

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