TY - JOUR

T1 - On dynamic coloring for planar graphs and graphs of higher genus

AU - Chen, Ye

AU - Fan, Suohai

AU - Lai, Hong Jian

AU - Song, Huimin

AU - Sun, Lei

N1 - Funding Information:
The second author’s work is partially supported by the National NSF of China (No. 11071089 ), and the Fundamental Research Funds for the Central Universities (No. 21611610 ). The fourth author’s research is partially supported by Natural Science Foundation of Shandong (No. ZR2011FQ035 ). The last author’s research is partially supported by a project of Shandong Province Higher Educational Science and Technology Program (J10LA11), and sponsored by the International Cooperation Program for Excellent Lectures of 2010 by Shandong Provincial Education Department, PR China.

PY - 2012/5

Y1 - 2012/5

N2 - 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)).

AB - 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)).

KW - (k, r)-coloring

KW - Dynamic choice number

KW - Dynamic chromatic number

KW - Heawood coloring theorem

KW - r-hued chromatic number

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

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

U2 - 10.1016/j.dam.2012.01.012

DO - 10.1016/j.dam.2012.01.012

M3 - Article

AN - SCOPUS:84862804581

VL - 160

SP - 1064

EP - 1071

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 7-8

ER -