A generalization of Noel-Reed-Wu theorem to signed graphs

DOI10.1016/J.DISC.2020.111833zbMATH Open1437.05092arXiv1810.09741OpenAlexW3003166427MaRDI QIDQ2174577FDOQ2174577

Authors: Wei Wang, Jianguo Qian 

Publication date: 21 April 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $Sigma$ be a signed graph where two edges joining the same pair of vertices with opposite signs are allowed. The zero-free chromatic number $ch{i}^{\ast }(Sigma)$ of $Sigma$ is the minimum even integer $2k$ such that $G$ admits a proper coloring $fcolon,V(Sigma)mapstopm1,pm2,ldots,pmk$. The zero-free list chromatic number $ch{i}_l^{\ast }(Sigma)$ is the list version of zero-free chromatic number. $Sigma$ is called zero-free chromatic-choosable if $ch{i}_l^{\ast }(Sigma)=ch{i}^{\ast }(Sigma)$. We show that if $Sigma$ has at most $ch{i}^{\ast }(Sigma)+1$ vertices then $Sigma$ is zero-free chromatic-choosable. This result strengthens Noel-Reed-Wu Theorem which states that every graph $G$ with at most $2chi(G)+1$ vertices is chromatic-choosable, where $chi(G)$ is the chromatic number of $G$.

Full work available at URL: https://arxiv.org/abs/1810.09741

Recommendations

• How colorful the signed graph?
• Degree choosable signed graphs
• Signed colouring and list colouring of k‐chromatic graphs
• The chromatic number of a signed graph
• Edge coloring signed graphs

zbMATH Keywords

list coloringsigned graphchromatic-choosable graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Cites Work

• Signed graph coloring
• On chromatic‐choosable graphs
• The chromatic number of a signed graph
• A proof of a conjecture of Ohba
• Degree choosable signed graphs
• Choosability in signed planar graphs

Cited In (3)

• Hajós-like theorem for signed graphs
• A counterexample to a conjecture of Wang and Hou on signed graphs
• How colorful the signed graph?

This page was built for publication: A generalization of Noel-Reed-Wu theorem to signed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174577)