For every integer r≥ 2, does there exist a constant c_r>0 and an infinite family of bipartite graphs B_n such that omega(B_n^r)→∞ and chi(B_n^r)≥ c_r,omega(B_n^r)^2 for all n, where B_n^r is the rth graph power? Equivalently, is the known quadratic upper bound chi(B^r)=O(omega(B^r)^2) asymptotically sharp for every r≥ 2?

Sharp quadratic χ-binding for powers of bipartite graphs

For every integer $r\ge 2$ , does there exist a constant $c_r>0$ and an infinite family of bipartite graphs $B_n$ such that $\omega(B_n^r)\to\infty$ and $\chi(B_n^r)\ge c_r\,\omega(B_n^r)^2$ for all $n$ , where $B_n^r$ is the $r$ th graph power? Equivalently, is the known quadratic upper bound $\chi(B^r)=O(\omega(B^r)^2)$ asymptotically sharp for every $r\ge 2$ ?

References

Primary source

arXiv

Additional references

Sharp quadratic χ-binding functions for powers of bipartite graphs — arXiv

graph-theory

4 days ago

Progress summary

Refreshed 4 days ago

Claimed solved

A new preprint claims that the best possible growth is quadratic for every power of a bipartite graph, including squares.

The problem asks whether the known quadratic upper bound for coloring powers of bipartite graphs is sharp for every $r \ge 2$ , including $r=2$ .

Known results

A 2023 preprint records the general quadratic upper bound for squares of bipartite graphs.
It gives bipartite graphs $B$ with $\chi(B^2)=\Omega\!\left(\frac{\omega(B^2)^2}{\log \omega(B^2)}\right)$ .
For convex bipartite graphs, it proves $\chi(G^2)\le \frac{3}{2}\omega(G^2)$ .
It states that squares of biconvex bipartite graphs are perfect.

August 27, 2026 claimed sharpness

A new preprint, “Sharp quadratic $\chi$ -binding functions for powers of bipartite graphs,” claims that the quadratic upper bound is best possible for every $r\ge 2$ , closing the previous gap, including the square case. This claim is unverified.

Current status (as of August 2026): A new preprint claims the quadratic bound is sharp for every $r \ge 2$ , but no independent verification is recorded.

Sources

No solutions have been posted yet.