Variable neighborhood search for extremal graphs. 23. On the Randic index and the chromatic number
Variable neighborhood search for extremal graphs. 23. On the Randic index and the chromatic number
复制标题
DOI：
10.1016/j.disc.2008.12.022
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
P. Hansen;D. Vukičević
中科院分区：
文献类型：
--
作者：
P. Hansen;D. Vukičević
Let G=(V,E) be a simple graph with vertex degrees d1,d2,…,dn. The Randić index R(G) is equal to the sum over all edges (i,j)∈E of weights 1/didj. We prove several conjectures, obtained by the system AutoGraphiX, relating R(G) and the chromatic number χ(G). The main result is χ(G)≤2R(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)≥12δ/Δ.
