The chromatic spectrum of signed graphs

Abstract

The chromatic number $\chi ((G,\sigma ))$ of a signed graph $(G,\sigma )$ is the smallest number $k$ for which there is a function $c:V(G)\to {\mathbb{Z}}_k$ such that $c(v)\ne \sigma (e)c(w)$ for every edge $e=vw$. Let $\Sigma (G)$ be the set of all signatures of $G$. We study the chromatic spectrum ${\Sigma }_{\chi }(G)=\{\chi ((G,\sigma )):\sigma \in \Sigma (G)\}$ of $(G,\sigma )$. Let $M_{\chi }(G)=\max \{\chi ((G,\sigma )):\sigma \in \Sigma (G)\}$, and $m_{\chi }(G)=\min \{\chi ((G,\sigma )):\sigma \in \Sigma (G)\}$. We show that ${\Sigma }_{\chi }(G)=\{k:m_{\chi }(G)\le k\le M_{\chi }(G)\}$. We also prove some basic facts for critical graphs. Analogous results are obtained for a notion of vertex-coloring of signed graphs which was introduced by Máčajová, Raspaud, and Škoviera.

6 pages

References in corpus (1)

• Circular coloring of signed graphs