PreprintarXiv licencearXiv
Explicit and logarithmically improved chromatic bounds for (P2∪ P3)-free graphs
Abstract
We prove that every (P2∪ P3)-free graph G, with k=ω(G), satisfies χ(G)=O (k3(lnln k)/(ln k)). Thus the class admits an o(k3) binding function. We also prove the explicit bound χ(G)≤ k3/8+5k2/4−4k+8 (k≥8), with a sharper formula for odd k. A further refinement gives an explicit cubic bound with leading coefficient 104/837<1/8.
Related
- Improved bounds on the b-chromatic number using the independence and chromatic numbers
- Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
- Improved explicit Burgess-strength bounds for composite moduli
- Improved Explicit and Algorithmic Lower Bounds for r(5,t)
- Small graphs without power-of-two cycles: a lower bound of 24, a correction to a construction of Exoo, and explicit bounds for f(k)
BibTeX
@misc{chen2026explicit,
title = {{Explicit and logarithmically improved chromatic bounds for $(P_2\cup P_3)$-free graphs}},
author = {Lizhong Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.23441},
eprint = {2607.23441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.23441},
}
RIS
TY - UNPB
TI - Explicit and logarithmically improved chromatic bounds for (P_2∪ P_3)-free graphs
AU - Lizhong Chen
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2607.23441
UR - https://arxiv.org/abs/2607.23441
AB - We prove that every (P_2∪ P_3)-free graph G, with k=ω(G), satisfies χ(G)=O (k^3(lnln k)/(ln k)). Thus the class admits an o(k^3) binding function. We also prove the explicit bound χ(G)≤ k^3/8+5k^2/4−4k+8 (k≥8), with a sharper formula for odd k. A further refinement gives an explicit cubic bound with leading coefficient 104/837<1/8.
ER -