Chromatic number of $\frac{3}{3}$-power of graph

Status partial high confidence

The conjecture $\chi(G^{3/3}) \leq 2\Delta(G)+1$ remains open in general. Anastos, Boyadzhiyska, Rathke, and Rué (2024) proved the asymptotically tight bound $\chi(G^{3/3}) \leq \Delta + C\log\Delta$ for all graphs $G$ (with $C=28$ for sufficiently large $\Delta$), which confirms the conjecture for all sufficiently large $\Delta$ and is in fact stronger than $2\Delta+1$ in that regime, but leaves the exact conjecture open for small-to-moderate values of $\Delta \geq 5$ not already handled by pre-posting results. Lower bounds show $\chi(G^{3/3}) \geq \Delta + \Omega(\log\Delta)$ for infinitely many $\Delta$, making the new upper bound essentially tight.

Cited literature (1)

• partial On the chromatic number of powers of subdivisions of graphs (2024)
  Michael Anastos, Simona Boyadzhiyska, Silas Rathke, Juanjo Rué · Discrete Applied Mathematics · arXiv:2404.05542 · doi:10.1016/j.dam.2024.10.002

  Proves $\chi(G^{3/3}) \leq \Delta + C\log\Delta$ for all graphs $G$ with maximum degree $\Delta$ (with $C=28$ for large $\Delta$), confirming the Mozafari-Nia–Iradmusa conjecture asymptotically for large $\Delta$ and establishing a matching $\Omega(\log\Delta)$ lower bound.

Reviewer notes. The DOI 10.1016/j.dam.2024.10.002 (Discrete Applied Mathematics, Vol. 360, pp. 506–511) was found in web search results and is consistent with the ISTA research-explorer metadata, but ScienceDirect returned HTTP 403 so the journal page could not be independently verified via WebFetch; the arXiv preprint is fully verified. A 2024 paper by Mozafari-Nia and Iradmusa on simultaneous coloring of hypercubes (Communications in Combinatorics and Optimization, Vol. 9(1), pp. 67–77) was mentioned in search results but the publisher's website was unreachable (ECONNREFUSED), so it was not cited. The Opuscula Mathematica paper on incidence coloring of graph fractional powers (vol. 43, no. 1) was also found but its PDF was binary-encoded and could not be read; it appears to predate the posting date in any case.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (web search enabled) · 235s.