PreprintarXiv licencearXiv
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)≤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.
Related
- Sparse chromatic graphs and the complete-graph triangle bound
- A double-logarithmic upper bound on the chromatic number of the associahedron
- An improved upper bound on the chromatic number of the n-dimensional sphere
- On the k-Distance Chromatic Number of Unicyclic Graphs
- An elementary proof of a tight Δ+1 bound for the additive chromatic number
BibTeX
@misc{wang2026cubic,
title = {{A cubic chromatic bound for capped graphs}},
author = {Hongyang Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37578},
eprint = {2610.37578},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37578},
}
RIS
TY - UNPB
TI - A cubic chromatic bound for capped graphs
AU - Hongyang Wang
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37578
UR - https://arxiv.org/abs/2610.37578
AB - 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)≤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.
ER -