The chromatic spectrum of signed graphs

详细信息    查看全文

• 作者：Yingli Kang¹ ; ^{yingli@mail.upb.de" class="auth_mail" title="E-mail the corresponding author} ; Eckhard Steffen ; ^{es@upb.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Signed graphs ; Chromatic number ; Vertex coloring ; Chromatic spectrum
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 November 2016
• 年：2016
• 卷：339
• 期：11
• 页码：2660-2663
• 全文大小：351 K

文摘

The chromatic number χ((G,σ))$\chi \left((G,\sigma )\right)$ of a signed graph (G,σ)$(G,\sigma )$ is the smallest number k$k$ for which there is a function c:V(G)→Z_k$c:V\left(G\right)\to {\mathbb{Z}}_k$ such that c(v)≠σ(e)c(w)$c\left(v\right)\ne \sigma \left(e\right)c\left(w\right)$ for every edge e=vw$e=vw$. Let Σ(G)$\Sigma \left(G\right)$ be the set of all signatures of G$G$. We study the chromatic spectrum ${\Sigma }_{\chi }\left(G\right)=\{\chi \left((G,\sigma )\right):\sigma \in \Sigma \left(G\right)\}$ of (G,σ)$(G,\sigma )$. Let $M_{\chi }\left(G\right)=max\{\chi \left((G,\sigma )\right):\sigma \in \Sigma \left(G\right)\}$, and $m_{\chi }\left(G\right)=min\{\chi \left((G,\sigma )\right):\sigma \in \Sigma \left(G\right)\}$. We show that ${\Sigma }_{\chi }\left(G\right)=\{k:m_{\chi }\left(G\right)\le k\le M_{\chi }\left(G\right)\}$. 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 in Máčajová et al. (2016).