TY - JOUR

T1 - Bounds on the Dynamic Chromatic Number of a Graph in Terms of its Chromatic Number

AU - Karpov, D. V.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - A vertex coloring of a graph is called dynamic if the neighborhood of any vertex of degree at least 2 contains at least two vertices of distinct colors. Similarly to the chromatic number X(G) of a graph G, one can define its dynamic number Xd(G) (the minimum number of colors in a dynamic coloring) and dynamic chromatic number X2(G) (the minimum number of colors in a proper dynamic coloring). We prove that X2(G) ≤ X(G).Xd(G) and construct an infinite series of graphs for which this bound on X2(G) is tight. For a graph G, set k=(G)We prove that X2(G) ≤ (k+1)c. Moreover, in the case where k ≥ 3 and Δ(G) ≥ 3, we prove the stronger bound X2(G) ≤ kc.

AB - A vertex coloring of a graph is called dynamic if the neighborhood of any vertex of degree at least 2 contains at least two vertices of distinct colors. Similarly to the chromatic number X(G) of a graph G, one can define its dynamic number Xd(G) (the minimum number of colors in a dynamic coloring) and dynamic chromatic number X2(G) (the minimum number of colors in a proper dynamic coloring). We prove that X2(G) ≤ X(G).Xd(G) and construct an infinite series of graphs for which this bound on X2(G) is tight. For a graph G, set k=(G)We prove that X2(G) ≤ (k+1)c. Moreover, in the case where k ≥ 3 and Δ(G) ≥ 3, we prove the stronger bound X2(G) ≤ kc.

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

U2 - 10.1007/s10958-018-3855-4

DO - 10.1007/s10958-018-3855-4

M3 - Article

AN - SCOPUS:85047329123

VL - 232

SP - 21

EP - 24

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 1

ER -