On dynamic coloring for planar graphs and graphs of higher genus

Ye Chen, Suohai Fan, Hong Jian Lai, Huimin Song, Lei Sun

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

For integers k,r>0, a (k,r)-coloring of a graph G is a proper coloring on the vertices of G by k colors such that every vertex v of degree d(v) is adjacent to vertices with at least mind(v),r different colors. The dynamic chromatic number, denoted by χ2(G), is the smallest integer k for which a graph G has a (k,2)-coloring. A list assignment L of G is a function that assigns to every vertex v of G a set L(v) of positive integers. For a given list assignment L of G, an (L,r)-coloring of G is a proper coloring c of the vertices such that every vertex v of degree d(v) is adjacent to vertices with at least mind(v),r different colors and c(v)∈L(v). The dynamic choice number of G, c h2(G), is the least integer k such that every list assignment L with |L(v)|=k, ∀v∈V(G), permits an (L,2)-coloring. It is known that for any graph G, χr(G)≤c hr(G). Using Euler distributions in this paper, we prove the following results, where (2) and (3) are best possible. If G is planar, then c h2(G)≤6. Moreover, c h2(G)≤5 when Δ(G)≤4.If G is planar, then χ2(G)≤5.If G is a graph with genus g(G)≥1, then c h2(G)≤12(7+1+48g(G)).

Original languageEnglish (US)
Pages (from-to)1064-1071
Number of pages8
JournalDiscrete Applied Mathematics
Volume160
Issue number7-8
DOIs
StatePublished - May 2012
Externally publishedYes

Keywords

  • (k, r)-coloring
  • Dynamic choice number
  • Dynamic chromatic number
  • Heawood coloring theorem
  • r-hued chromatic number

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On dynamic coloring for planar graphs and graphs of higher genus'. Together they form a unique fingerprint.

Cite this