Dom-Coloring of Grids: Exact Results and a General Conjecture

Dom-Coloring of Grids

Abstract

A proper coloring of a graph \( G \) is called a \emph{dom-coloring} if there exists a dominating set that includes at least one vertex from each color class. The cardinality of a smallest such dominating set is known as the \emph{dom-chromatic number} of \( G \). The central question of the dom-coloring problem is: how few vertices are needed to dominate \( G \) under a proper coloring, and what is the exact value of its dom-chromatic number? In this paper, we present a complete classification of all graphs \( G \) whose dom-coloring problem is resolved by selecting exactly \( |G| - 1 \) vertices. Moreover, we derive exact values of the dom-chromatic number for three families of grid graphs of the form \( P_m \square P_n \), with \( n \geq 2 \) and \( m \in \{3, 4, 5\} \). Our study extends prior results in the literature and concludes with a general conjecture on the dom-coloring of arbitrary grids.