The Singular Chromatic Number of a Graph

Abstract

A proper coloring of a graph \(G\) assigns colors to vertices such that adjacent vertices receive distinct colors. The minimum number of colors is the chromatic number \(\chi(G)\). For a graph \(G\) and a proper coloring \(c: V(G) \to \{1, 2, \ldots, k\}\), the color code of a vertex \(v\) is \(code(v) = (c(v), S_v)\), where \(S_v = \{c(u): u \in N(v)\}\). Coloring \(c\) is \emph{singular} if distinct vertices have distinct color codes, and the \emph{singular chromatic number} \(\chi_s(G)\) is the minimum positive integer \(k\) for which \(G\) has a singular \(k\)-coloring. Thus, \(\chi(G) \leq \chi_{si}(G) \leq n\) for every graph \(G\) of order \(n\). We establish a characterization for all triples \((a, b, n)\) of positive integers for which there exists a graph \(G\) of order \(n\) with \(\chi(G) = a\) and \(\chi_{si}(G) = b\). Furthermore, for every vertex \(v\) and edge \(e\) in \(G\), we show:
\( \chi_{si}(G) – 1 \leq \chi_{si}(G – v) \leq \chi_{si}(G) + \deg(v) \) and
\( \chi_{si}(G) – 1 \leq \chi_{si}(G – e) \leq \chi_{si}(G) + 2, \)
and prove that these bounds are sharp. Additionally, we determine the singular chromatic numbers of cycles and paths.