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
SN - 0166-218X
VL - 160
SP - 1064
EP - 1071
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 7-8
ER -