no. 4 · Wednesday 28 October 2026
A cubic chromatic bound for capped graphs
Abstract
An ordered graph is capped if, for any four vertices $a<b<c<d$, the edges $ac$ and $bd$ imply the edge $ad$. We prove that every nonempty capped graph $G$ satisfies $χ(G)\leq\min\{3^{ω(G)-1},18ω(G)^3\}$, where $χ(G)$ and $ω(G)$ are its chromatic number and clique number. This proves a conjecture of Davies, Krawczyk, McCarty and Walczak.
- comments
- 10 pages
- fields
- Combinatorics