A Stronger Relation Between Coloring Number and the Modification of Randić Index

Abstract

The coloring number \(col(G)\) of a graph \(G\) is the smallest number \(k\) for which there exists a linear ordering of the vertices of \(G\) such that each vertex is preceded by fewer than \(k\) of its neighbors. It is well known that \(\chi(G) \leq col(G)\) for any graph \(G\), where \(\chi(G)\) denotes the chromatic number of \(G\). The Randić index \(R(G)\) of a graph \(G\) is defined as the sum of the weights \(\frac{1}{\sqrt{d(u)d(v)}}\) of all edges \(uv\) of \(G\), where \(d(u)\) denotes the degree of a vertex \(u\) in \(G\). We show that \(\chi(G) \leq col(G) \leq 2R'(G) \leq R(G)\) for any connected graph \(G\) with at least one edge, and \(col(G) = 2R'(G)\) if and only if \(G\) is a complete graph with some pendent edges attaching to its same vertex, where \(R'(G)\) is a modification of Randić index, defined as the sum of the weights \(\frac{1}{\max\{d(u), d(v)\}}\) of all edges \(uv\) of \(G\). This strengthens a relation between Randić index and chromatic number by Hansen et al. [7], a relation between Randić index and coloring number by Wu et al. [17] and extends a theorem of Deng et al. [2].