TY - JOUR

T1 - Graph r-hued colorings—A survey

AU - Chen, Ye

AU - Fan, Suohai

AU - Lai, Hong Jian

AU - Xu, Murong

N1 - Funding Information:
This research is supported in part by National Natural Science Foundation of China (Grant No. 11771039 and 11771443 ), by National Key R&D Program of China ( 2020YFA0712500 ), and by Guangdong Basic and Applied Basic Research Foundation ( 2022A1515011267 ).
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/11/15

Y1 - 2022/11/15

N2 - A (k,r)-coloring of a graph G is a proper k-vertex coloring of G such that the neighbors of each vertex of degree d will receive at least min{d,r} different colors. The r-hued chromatic number, denoted by χr(G), is the smallest integer k for which a graph G has a (k,r)-coloring. This article is intended to survey the recent developments on the studies related to this r-hued colorings. Emphases are on the r-hued colorings of planar graphs, graph families with forbidden minors, and sparse graphs, as well as on the comparison between the r-hued chromatic number and the chromatic number of a graph, and the sensitivity studies of the r-hued chromatic number. It also surveys other related results on r-hued colorings and list r-hued colorings.

AB - A (k,r)-coloring of a graph G is a proper k-vertex coloring of G such that the neighbors of each vertex of degree d will receive at least min{d,r} different colors. The r-hued chromatic number, denoted by χr(G), is the smallest integer k for which a graph G has a (k,r)-coloring. This article is intended to survey the recent developments on the studies related to this r-hued colorings. Emphases are on the r-hued colorings of planar graphs, graph families with forbidden minors, and sparse graphs, as well as on the comparison between the r-hued chromatic number and the chromatic number of a graph, and the sensitivity studies of the r-hued chromatic number. It also surveys other related results on r-hued colorings and list r-hued colorings.

KW - Distance colorings

KW - List r-hued chromatic number

KW - r-hued chromatic number

UR - http://www.scopus.com/inward/record.url?scp=85133258367&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85133258367&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2022.06.003

DO - 10.1016/j.dam.2022.06.003

M3 - Review article

AN - SCOPUS:85133258367

VL - 321

SP - 24

EP - 48

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -