Group for Research in Decision Analysis

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

## Pierre Hansen and Damir Vukicevic

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}$.

, 16 pages