A generalization of Noel-Reed-Wu Theorem to signed graphs
read the original 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^*(\Sigma)$ of $\Sigma$ is the minimum even integer $2k$ such that $G$ admits a proper coloring $f\colon\,V(\Sigma)\mapsto \{\pm 1,\pm 2,\ldots,\pm k\}$. The zero-free list chromatic number $\chi^*_l(\Sigma)$ is the list version of zero-free chromatic number. $\Sigma$ is called zero-free chromatic-choosable if $\chi^*_l(\Sigma)=\chi^*(\Sigma)$. We show that if $\Sigma$ has at most $\chi^*(\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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.