Upper Bounds of Dynamic Chromatic Number

Abstract

A proper vertex \(k\)-coloring of a graph \(G\) is dynamic if for every vertex \(v\) with degree at least \(2\), the neighbors of \(v\) receive at least two different colors. The smallest integer \(k\) such that \(G\) has a dynamic \(k\)-coloring is the dynamic chromatic number \(\chi_d(G)\). We prove in this paper the following best possible upper bounds as an analogue to Brook’s Theorem, together with the determination of chromatic numbers for complete \(k\)-partite graphs.

1. If \(\Delta \leq 3\), then \(\chi_d(G) \leq 4\), with the only exception that \(G = C_5\), in which case \(\chi_d(C_5) = 5\).
2. If \(\Delta \geq 4\), then \(\chi_d(G) \leq \Delta + 1\).
3. \(\chi_d(K_{1,1}) = 2\), \(\chi_d(K_{1,m}) = 3\) and \(\chi_d(K_{m,n}) = 4\) for \(m, n \geq 2\); \(\chi_d(K_{k,n_1,n_2,\ldots,n_k}) = k\) for \(k \geq 3\).