Optimal binding function for (cap,even hole)-free graphs with no short odd holes

Chenglong Deng; Xuding Zhu; Xuding zhu

combinatorics

Optimal binding function for (cap,even hole)-free graphs with no short odd holes

arXiv:2607.27850

summary

The paper proves that for any graph without caps, even holes, and short odd holes, the chromatic number is bounded by ⌈(2q+1)/(2q)·ω(G)⌉ for all q ≥ 3, confirming a conjectured optimal binding function.

Abstract

A hole in a graph is an induced cycle of length at least $4$ . A cap is a hole together with a vertex adjacent to exactly two consecutive vertices of it. Chen, Xu and Xu conjectured that if $q \geq 2$ and $G$ is a $(cap, even hole)$ -free graph with no odd hole of length at most $2 q - 1$ , then $I ¨ (G) \leq ⌈ \frac{2 q + 1}{2 q} I ¨ (G) ⌉ .$ They confirmed the conjecture for $q \leq 3$ . In this paper, we prove the conjecture for all $q \geq 3$ . As a corollary, we prove that for such a graph $G$ , $I ¨ _{f} (G) \leq \frac{2 q + 1}{2 q} I ¨ (G) .$

Topics & keywords

#graph coloring #hole‑free graphs #cap‑free graphs #even holes #chromatic number boundschromatic numberfractional chromatic numbercapeven holeodd holebinding function