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,\dots ,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)\le {\chi }_{si}(G)\le 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\le {\chi }_{si}(G–v)\le {\chi }_{si}(G)+\mathrm{deg}(v)$ and
${\chi }_{si}(G)–1\le {\chi }_{si}(G–e)\le {\chi }_{si}(G)+2,$
and prove that these bounds are sharp. Additionally, we determine the singular chromatic numbers of cycles and paths.