Skip to content
Preprint

A cubic chromatic bound for capped graphs

Oct 2026 · 0 citations · 7 references
Mathematics

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 $\chi(G)\leq\min\{3^{\omega(G)-1},18\omega(G)^3\}$, where $\chi(G)$ and $\omega(G)$ are its chromatic number and clique number. This proves a conjecture of Davies, Krawczyk, McCarty and Walczak.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.