The =5=5 case of Vizing's conjecture for triangle-free graphs

At least 2 years old · documented by

Let GG be a 55-regular triangle-free graph.

The =5=5 case of Vizing's conjecture. Every 55-regular triangle-free graph has chromatic number at most 44.

This is identified in the source as the current smallest open case of the broader triangle-free graph coloring conjecture. The source notes that the corresponding bound is known for maximum degree at most 44, but this 55-regular case was presented as open.

References

Primary source

Ross J. Kang and Matthieu Rosenfeld, “On Vizing's problem for triangle-free graphs”, arXiv:2309.10876 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.