Abstract: A dynamic coloring of a graph $G$ is a proper coloring such that for every vertex $v \in V(G)$ of degree at least 2, the neighbors of $v$ receive at least 2 colors. It was conjectured by B. Montgomery in 2001 that if $G$ is a $k$-regular graph, then $\chi_2(G) - \chi(G) \leq 2$. In this paper, we prove that if $G$ is a $k$-regular graph with $\chi(G) \geq 4$, then $\chi_2(G) \leq \chi(G) + \alpha(G^2)$. This result confirms the conjecture for all regular graphs $G$ with diameter at most 2 and $\chi(G) \geq 4$, showing that $\chi_2(G) - \chi(G) \leq 1$ in these cases. Moreover, we demonstrate that for any $k$-regular graph $G$, $\chi_2(G) - \chi(G) \leq 6\ln k + 2$. Finally, we show that for any $n$, there exists a regular graph $G$ whose chromatic number is $n$ and $\chi_2(G) - \chi(G) \geq 1$, providing a negative answer to a conjecture by Ahadi et al.
Introduction
In the study of graph theory, standard vertex coloring seeks to assign colors to vertices such that no two adjacent vertices share the same color. The minimum number of colors required for such a coloring is the chromatic number, denoted as $\chi(G)$.
Dynamic coloring introduces an additional "diversity" constraint: for every vertex $v$ with a degree of at least 2, its neighborhood $N(v)$ must contain at least two different colors. The minimum number of colors required to satisfy both the standard and dynamic constraints is the dynamic chromatic number, $\chi_2(G)$. This paper investigates the relationship between $\chi(G)$ and $\chi_2(G)$, specifically focusing on $k$-regular graphs—graphs where every vertex has exactly $k$ neighbors.
The Montgomery Conjecture
The central motivation for this research is the Montgomery Conjecture (2001), which posits that for any $k$-regular graph, the difference between the dynamic and standard chromatic numbers is at most 2:
$$\chi_2(G) - \chi(G) \leq 2$$
While this conjecture has remained open for two decades, this paper provides significant evidence in its favor and establishes new upper bounds for the general case.
Key Results
1. Graphs with Small Diameter
One of the paper's primary contributions is the confirmation of Montgomery's conjecture for graphs with a diameter of at most 2. The diameter of a graph is the maximum shortest path between any two vertices. For $k$-regular graphs with $diam(G) \leq 2$ and $\chi(G) \geq 4$, the author proves:
$$\chi_2(G) - \chi(G) \leq 1$$
This result suggests that in dense or well-connected regular graphs, the dynamic constraint is remarkably easy to satisfy, often requiring at most one additional color beyond the standard chromatic number.
2. Improved General Bounds
For $k$-regular graphs in general, the paper establishes a new upper bound using probabilistic methods:
$$\chi_2(G) - \chi(G) \leq 6\ln k + 2$$
This is a substantial improvement over the previous best-known bound of $14.06\ln k + 1$. It demonstrates that the "penalty" for the dynamic constraint grows only logarithmically with the degree of the graph, rather than linearly.
3. Relationship with the Independence Number of $G^2$
The author establishes a link between dynamic coloring and the independence number of the square of the graph, $\alpha(G^2)$. Specifically, for regular graphs with $\chi(G) \geq 4$:
$$\chi_2(G) \leq \chi(G) + \alpha(G^2)$$
Since $\alpha(G^2)$ represents the size of the largest set of vertices where no two vertices are within distance 2 of each other, this bound provides a structural way to manage "bad" neighborhoods where the dynamic constraint might fail.
4. Counterexamples to the Ahadi et al. Conjecture
Previous researchers (Ahadi et al.) conjectured that for certain classes of graphs, the dynamic chromatic number might always equal the standard chromatic number. This paper provides a definitive negative answer by constructing regular graphs for any integer $n$ where $\chi(G) = n$ but $\chi_2(G) > \chi(G)$.
Methodology
The proofs in this paper rely on a sophisticated combination of combinatorial and probabilistic tools:
- Lovász Local Lemma (LLL): This probabilistic tool is used to show that a valid dynamic coloring exists by proving that the probability of all "bad" events (vertices failing the dynamic constraint) is strictly greater than zero.
- Hypergraph 2-Colorability: The problem of resolving "bad" neighborhoods is mapped onto a hypergraph. If the hypergraph is 2-colorable, the neighborhoods can be partitioned to satisfy the dynamic constraint with minimal extra colors.
- Graph Products: The author utilizes Categorical and Cartesian products to construct the counterexamples mentioned above, allowing for the creation of regular graphs with precisely controlled coloring properties.
Conclusion and Future Work
This research significantly narrows the gap in our understanding of dynamic coloring in regular graphs. While the $6\ln k$ bound is a major advancement, the original Montgomery Conjecture—suggesting a constant difference of 2—remains the ultimate goal. Additionally, the behavior of 3-chromatic regular graphs ($\chi(G) = 3$) remains an area for further investigation, as the current primary results assume $\chi(G) \geq 4$.
Summary updated