2025/04/02 by Chen, Ran, Xu, Baogang
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2504.01808
A \em hole is an induced cycle of length at least 4, a k-hole is a hole of length k, and an \em odd hole is a hole of odd length. Let ℓ≥ 2 be an integer. Let \cal Aℓ be the family of graphs of girth at least 2ℓ and having no odd holes of length at least 2ℓ+3, let \cal Bℓ be the triangle-free graphs which have no 5-holes and no odd holes of length at least 2ℓ+3, and let \cal Gℓ be the family of graphs of girth 2ℓ+1 and have no odd hole of length at least 2ℓ+5. Chudnovsky \em et al. \citeCSS2016 proved that every graph in \cal A2 is 58000-colorable, and every graph in \cal Bℓ is (ℓ+1)4ℓ-1-colorable. Lan and liu \citeLL2023 showed that for ℓ≥3, every graph in \cal Gℓ is 4-colorable. It is not known whether there exists a small constant c such that graphs of \cal G2 are c-colorable. In this paper, we show that every graph in \cal G2 is 1456-colorable, and every graph in \cal A3 is 4-colorable. We also show that every 7-hole free graph in \cal Bℓ is (12ℓ+8)-colorable.