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)\le 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)\le col(G)\le 2R^{\prime }(G)\le R(G)$ for any connected graph $G$ with at least one edge, and $col(G)=2R^{\prime }(G)$ if and only if $G$ is a complete graph with some pendent edges attaching to its same vertex, where $R^{\prime }(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].