Graph r-hued colorings—A survey

Ye Chen, Suohai Fan, Hong Jian Lai, Murong Xu

Research output: Contribution to journalReview articlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)24-48
Number of pages25
JournalDiscrete Applied Mathematics
Volume321
DOIs
StatePublished - Nov 15 2022

Keywords

  • Distance colorings
  • List r-hued chromatic number
  • r-hued chromatic number

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Graph r-hued colorings—A survey'. Together they form a unique fingerprint.

Cite this