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

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 ${\chi }^{\ast }(\Sigma )$ of $\Sigma$ is the minimum even integer $2k$ such that $G$ admits a proper coloring $f:V(\Sigma )\mapsto \{\pm 1,\pm 2,\dots ,\pm k\}$. The zero-free list chromatic number ${\chi }_l^{\ast }(\Sigma )$ is the list version of zero-free chromatic number. $\Sigma$ is called zero-free chromatic-choosable if ${\chi }_l^{\ast }(\Sigma )={\chi }^{\ast }(\Sigma )$. We show that if $\Sigma$ has at most ${\chi }^{\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 $2\chi (G)+1$ vertices is chromatic-choosable, where $\chi (G)$ is the chromatic number of $G$.

24 pages