zbMATH — the first resource for mathematics

The chromatic spectrum of signed graphs. (English) Zbl 1339.05169
Summary: 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) \neq \sigma(e) c(w)\) for every edge \(e = v w\). Let \(\varSigma(G)\) be the set of all signatures of \(G\). We study the chromatic spectrum \(\varSigma_\chi(G) = \{\chi((G, \sigma)) : \sigma \in \varSigma(G) \}\) of \((G, \sigma)\). Let \(M_\chi(G) = \max \{\chi((G, \sigma)) : \sigma \in \varSigma(G) \}\), and \(m_\chi(G) = \min \{\chi((G, \sigma)) : \sigma \in \varSigma(G) \}\). We show that \(\varSigma_\chi(G) = \{k : m_\chi(G) \leq k \leq 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 E. Máčajová et al. [Electron. J. Comb. 23, No. 1, Research Paper P1.14, 10 p. (2016; Zbl 1329.05116)].

05C22 Signed and weighted graphs
05C15 Coloring of graphs and hypergraphs
Full Text: DOI arXiv
[1] Y. Kang, E. Steffen, Circular coloring of signed graphs, 2015. arXiv:1509.04488. · Zbl 1383.05103
[2] Máčajová, E.; Raspaud, A.; Škoviera, M., The chromatic number of a signed graph, Electron. J. Combin., 23, 1, #P1.14, (2016) · Zbl 1329.05116
[3] Raspaud, A.; Zhu, X., Circular flow on signed graphs, J. Combin. Theory Ser. B, 101, 464-479, (2011) · Zbl 1408.05068
[4] T. Schweser, M. Stiebitz, Degree choosable signed graphs, 2015. arXiv:1507.04569. · Zbl 1357.05055
[5] Zaslavsky, T., Chromatic invariants of signed graphs, Discrete Math., 42, 287-312, (1982) · Zbl 0498.05030
[6] Zaslavsky, T., Signed graph coloring, Discrete Math., 39, 215-228, (1982) · Zbl 0487.05027
[7] Zaslavsky, T., How colorful the signed graph?, Discrete Math., 52, 279-284, (1984) · Zbl 0554.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.