Paperlane

no. 5 · Friday 30 October 2026

Explicit and logarithmically improved chromatic bounds for $(P_2\cup P_3)$-free graphs

Lizhong Chen

math.CO · v5 · 16 pp

Abstract

We prove that every $(P_2\cup P_3)$-free graph $G$, with $k=ω(G)$, satisfies \[ χ(G)=O\!\left(k^3\frac{\ln\ln k}{\ln k}\right). \] Thus the class admits an $o(k^3)$ binding function. We also prove the explicit bound \[ χ(G)\le \frac{k^3}{8}+\frac{5k^2}{4}-4k+8 \qquad(k\ge8), \] with a sharper formula for odd $k$. A further refinement gives an explicit cubic bound with leading coefficient $104/837<1/8$.

comments
16 pages. Proofs simplified and exposition revised. Main results unchanged. The earlier row estimates and the quadratic bound under a rank-gap condition are not reproduced here; see v3 for those results
fields
Combinatorics
pdf ↗ page arXiv:2607.23441 ↗