Graphs with girth 8 and without longer even holes are 3-colorable
classification
🧮 math.CO
keywords
colorableeverygraphbigcupevengirthgraphschen
read the original abstract
For an integer $\ell\geq 2$, let ${\cal{H}}_{\ell}$ denote the family of graphs which have girth $2\ell$ and have no even hole of length greater than $2\ell$. Wu, Xu and Xu conjectured that every graph in $\bigcup_{\ell\geq 2} {\cal{H}}_{\ell}$ is $3$-colorable. Chen showed that every graph in $\bigcup_{\ell\geq 5} {\cal{H}}_{\ell}$ is $3$-colorable. In this paper, we prove that every graph in ${\cal{H}}_4$ is $3$-colorable.
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.