Explicit and logarithmically improved chromatic bounds for $(P_2\cup P_3)$-free graphs
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 and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.23441
curl -X POST /api/v1/records/arxiv/2607.23441/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.23441/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'