Dynamic Coloring (2001)

Originator: B. Montgomery    (presented by A. Kostochka and S.-J. Kim - REGS 2009)

Definitions: Montgomery [M] defined a dynamic coloring of a graph G to be a proper coloring in which each vertex neighborhood of size at least 2 receives at least two distinct colors. The dynamic chromatic number χd(G) is the least number of colors in such a coloring of G.

Background: The dynamic chromatic number is not a monotone parameter: it is 5 for a 5-cycle, but it is 4 for the graph obtained by adding one chord to a 5-cycle. It is trivially at least the chromatic number and can be that small; the dynamic chromatic number of a complete k-partite graph is k when k≥3 [LMP] (for a bipartite graph containing C4, at least four colors are needed). Lai, Montgomery, and Poon [LMP] proved that χd(G)≤Δ(G)+1 except when G=C5. Equality holds for the graph obtained from a complete graph by subdividing every edges once; since this graph is bipartite, there is no bound on χd(G) in terms of χ(G).

Conjecture 1: (Montgomery [M]) If G is a regular graph, then χd(G)≤χ(G)+2.

Comments: Akbari, Ghanbari, and Jahanbekam [AGJ1] proved several results bounding the dynamic chromatic number of regular graphs in terms of the ordinary chromatic number.

  • If G is bipartite and regular, then χd(G)≤χ(G)+2. (this involves 2-coloring the hypergraph of vertex neighborhoods in each partite set).
  • If G is strongly regular and G∉{C4,C5,Kr,r}, then χd(G)≤χ(G)+1.
  • If G is regular, then χd(G)≤2χ(G).
  • If G is regular, then χd(G)≤χ(G)+⌈α(G)/2⌉+1.

    • To exclude the extremal graphs (subdivision of complete graphs), one can require δ(G)≥k, hoping that making k large enough will make χd(G) bounded. However, Kim and Park [KP] observed that no such k suffices. Let G(n,k) be the X,Y-bigraph defined as follows: X=[n], Y is the family of k-element subsets of [n], and xy∈E(G) if and only if x∈y. Note that δ(G(n,k))=k and χd(G)>n/k.

    As a generalization of the problem for regular graphs, one can consider dynamic coloring for graphs where the maximum degree is not much larger than the minimum degree. For bipartite graphs with Δ(G)≤2δ(G), Kim and Park [KP] proved that χd(G)≤22 if δ(G)≥3; also χd(G)≤6 if δ(G)≥7, and χd(G)≤4 if δ(G)≥12.

    There is also a list version of dynamic coloring, like the list version of ordinary coloring. The list chromatic number of G, written ch(G), is the least k such that for any assignment of k-element lists to the vertices of G, there is a proper coloring of G where the color on each vertex is chosen from its list. The definition of the list dynamic chromatic number chd(G) is the same with "proper" replaced by "dynamic".

    Akbari, Ghanbari, and Jahanbekam [AGJ2] proved that if Δ(G)≥3 and G does not have C5 as a component, then chd(G)≤Δ(G)+1. This strengthens the result of [LMP] that χd(G)≤Δ(G)+1. They conjectured that for any graph G, chd(G)=max{ch(G),χd(G)}, but this was disproved by Esperet [E], who found a small planar bipartite graph with ch(G)=χd(G)=3 and chd(G)=4 and for k≥5 constructed bipartite graphs with ch(G)=χd(G)=3 and chd(G)≥k.

    References:
    [AGJ1] S. Akbari, M. Ghanbari, and S. Jahanbekam, On the dynamic chromatic number of regular graphs, preprint (presented at BCC22, 2009).
    [AGJ2] S. Akbari, M. Ghanbari, and S. Jahanbekam, On the list dynamic coloring of graphs. Discrete Appl. Math., in press.
    [E] L. Esperet, Dynamic list coloring of bipartite graphs, preprint at http://kam.mff.cuni.cz/~esperet/articles/dynamic.pdf .
    [KP] S.-J. Kim and W.-J. Park, private communication.
    [LMP] Lai, Hong-Jian; Montgomery, Bruce; Poon, Hoifung; Upper bounds of dynamic chromatic number. Ars Combin. 68 (2003), 193--201.
    [M] B. Montgomery, "Dynamic Coloring", Ph.D. Dissertation, West Virginia University, 2001.