Reed's bound for the chromatic number
For a finite nonempty simple graph $G$ write $\chi(G)$ for its chromatic number, $\Delta(G)$ for its maximum degree and $\omega(G)$ for its clique number, so that $\omega(G) \le \chi(G) \le \Delta(G) + 1$. The bound below is the average of these two bounds, rounded up; the rounding is needed, since the $5$-cycle has $\Delta = \omega = 2$ and $\chi = 3$. Reed proved that there is an $\varepsilon > 0$ such that $\chi(G) \le \lceil (1 - \varepsilon)(\Delta(G) + 1) + \varepsilon\, \omega(G) \rceil$ for every graph $G$, and Bonamy, Perrett and Postle that $\varepsilon = 1/26$ suffices when $\Delta(G)$ is large enough. King and Reed proved the bound below for all claw-free graphs.
Problem. Is $$\chi(G) \le \left\lceil \frac{\Delta(G) + 1 + \omega(G)}{2} \right\rceil$$ for every finite nonempty simple graph $G$?
Source: Reed (1998); see King and Reed (2015), Conjecture 1.1, and Bonamy, Perrett and Postle (2022), Conjecture 1.1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, chromatic number, graph colorings
References
@article{reed1998,
author = {Reed, Bruce},
title = {$\omega$, $\Delta$, and $\chi$},
journal = {J. Graph Theory},
volume = {27},
number = {4},
year = {1998},
pages = {177--212},
doi = {10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K},
}
@article{king2015,
author = {King, Andrew D. and Reed, Bruce A.},
title = {Claw-free graphs, skeletal graphs, and a stronger conjecture on $\omega$, $\Delta$, and $\chi$},
journal = {J. Graph Theory},
volume = {78},
number = {3},
year = {2015},
pages = {157--194},
doi = {10.1002/jgt.21797},
eprint = {1212.3036},
archivePrefix = {arXiv},
}
@article{bonamy2022,
author = {Bonamy, Marthe and Perrett, Thomas and Postle, Luke},
title = {Colouring graphs with sparse neighbourhoods: bounds and applications},
journal = {J. Combin. Theory Ser. B},
volume = {155},
year = {2022},
pages = {278--317},
doi = {10.1016/j.jctb.2022.01.009},
eprint = {1810.06704},
archivePrefix = {arXiv},
}
@misc{aim-reed-colouring,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Reed's bound for the chromatic number}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/337-reed-colouring.md},
note = {Entry 337 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00377, "Reed's bound for the chromatic number", clopen.solutions.