Dynamic Chromatic Number of Bipartite Graphs
Sasan Saqaeeyan, Esmaiel Mollaahamdi · Scientific Annals of Computer Science · 2016
A dynamic coloring of a graph G is a proper vertex coloring such that for every vertex v ∈ V (G) of degree at least 2, the neighbors of v receive at least 2 colors.The smallest integer k such that G has a dynamic coloring with k colors, is called the dynamic chromatic number of G and denoted by χ 2 (G).Montgomery conjectured that for every r-regular graph G, χ 2 (G)χ(G) ≤ 2 [19].Finding an optimal upper bound for χ 2 (G)χ(G) seems to be an intriguing problem.We show that there is a constant d such that every bipartite graph2 +k * .Among other results, we prove that for a given bipartite graph G = [X, Y ], determining whether G has a dynamic 4coloring ℓ : V (G) → {a, b, c, d} such that a, b are used for part X and c, d are used for part Y is NP-complete.