2508.07034

Total: 1

#1 Optimal $\chi$-boundness of $\ell$-holed graphs [PDF] [Copy] [Kimi] [REL]

Authors: Yan Wang, Rong Wu

A graph is {\em{$\ell$-holed}} if all of its induced cycles of length at least four have length exactly $\ell$. In the paper, we prove that if $G$ is an $\ell$-holed graph with odd $\ell\geq 7$, then $\chi(G)\leq {\lceil {\ell \over {\ell-1}}\omega(G) \rceil}$. This result is sharp.

Subject: Combinatorics

Publish: 2025-08-09 16:13:21 UTC