Graphs with girth 2ℓ+12\ell+1 and without longer odd holes that contain an odd K4K_4-subdivision

preprint2023arXivOpen access

Abstract

We say that a graph GG has an {\em odd K4K_4-subdivision} if some subgraph of GG is isomorphic to a K4K_4-subdivision and whose faces are all odd holes of GG. For a number ℓ≥2\ell\geq 2, let Gℓ\mathcal{G}_{\ell} denote the family of graphs which have girth 2ℓ+12\ell+1 and have no odd hole with length greater than 2ℓ+12\ell+1. Wu, Xu and Xu conjectured that every graph in ⋃ℓ≥2Gℓ\bigcup_{\ell\geq2}\mathcal{G}_{\ell} is 3-colorable. Recently, Chudnovsky et al. and Wu et al., respectively, proved that every graph in G2\mathcal{G}_2 and G3\mathcal{G}_3 is 3-colorable. In this paper, we prove that no 44-vertex-critical graph in ⋃ℓ≥5Gℓ\bigcup_{\ell\geq5}\mathcal{G}_{\ell} has an odd K4K_4-subdivision. Using this result, Chen proved that all graphs in ⋃ℓ≥5Gℓ\bigcup_{\ell\geq5}\mathcal{G}_{\ell} are 3-colorable.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.