Variable Neighborhood Search for Extremal Graphs. 23. On the Randic Index and the Chromatic Number

Hansen, Pierre; Vukicevic, Damir

Let $G=(V,E)$ be a simple graph with vertex degrees $d_1, d_2, \ldots, d_n$ . The Randic index $R(G)$ is equal to the sum over all edges $(i,j)\in E$ of weights $1/\sqrt{d_i d_j}$ . We prove several conjectures, obtained by the system AutoGraphiX, relating $R(G)$ and the chromatic number $\chi(G)$ . The main result is $\chi(G)\leq 2R(G)$ . To prove it, we also show that if $v\in V$ is a vertex of minimum degree $\delta$ of $G$ , $G-v$ the graph obtained from $G$ by deleting $v$ and all incident edges, and $\Delta$ the maximum degree of $G$ , then $R(G)-R(G-v)\geq \frac{1}{2} \sqrt{\delta/\Delta}$ .

Published October 2006 , 16 pages