no. 5 · Friday 30 October 2026
Explicit and logarithmically improved chromatic bounds for $(P_2\cup P_3)$-free graphs
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