On the Dynamic Coloring of Strongly Regular Graphs

Abstract

A proper vertex coloring of a graph \(G\) is called a dynamic coloring if for every vertex \(v\) with degree at least 2, the neighbors of \(v\) receive at least two different colors. It was conjectured that if \(G\) is a regular graph, then \(\chi_2(G) – \chi(G) \leq 2\). In this paper, we prove that, apart from the cycles \(C_4\) and \(C_5\) and the complete bipartite graphs \(K_{n,n}\), every strongly regular graph \(G\) satisfies \(\chi_2(G) – \chi(G) \leq 1\).