Upper bounds for the achromatic and coloring numbers of a graph

详细信息    查看全文

• 作者：Baoyindureng Wu^a ; ^{wubaoyin@hotmail.com} ; Clive Elphick ^{clive.elphick@gmail.com}
• 关键词：Chromatic number ; Coloring number ; Achromatic number ; Randić index
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：375-380
• 全文大小：385 K
• 卷排序：217

文摘

Dvořák et al. introduced a variant of the Randić index of a graph GG, denoted by R′(G)R′(G), where R′(G)=∑uv∈E(G)1max{d(u),d(v)}, and d(u)d(u) denotes the degree of a vertex uu in GG. The coloring number col(G)col(G) of a graph GG is the smallest number kk for which there exists a linear ordering of the vertices of GG such that each vertex is preceded by fewer than kk of its neighbors. It is well-known that χ(G)≤col(G)χ(G)≤col(G) for any graph GG, where χ(G)χ(G) denotes the chromatic number of GG. In this note, we show that for any graph GG without isolated vertices, col(G)≤2R′(G)col(G)≤2R′(G), with equality if and only if GG is obtained from identifying the center of a star with a vertex of a complete graph. This extends some known results. In addition, we present some new spectral bounds for the coloring and achromatic numbers of a graph.