← All problems

Wild-number conjecture for minimum proper colorings of complete graphs

Let w(Kn,φ)w(K_n,\varphi) denote the wild number of a properly edge-colored complete graph KnK_n, and let φ\varphi range over proper edge-colorings using the minimum possible number of colors. The conjecture is that, for every n≥3n\ge 3, the general lower bound L(n)L(n) established for these wild numbers is sharp; equivalently, the minimum wild number among minimum proper colorings satisfies min⁡φw(Kn,φ)=L(n)\min_{\varphi} w(K_n,\varphi)=L(n). The conjecture is known for 3≤n≤123\le n\le 12, but remains open for general nn.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new paper proves a lower bound and checks the conjecture for complete graphs of sizes three through twelve, but the proposed formula for all sizes remains unproved.

The wild-number conjecture concerns the minimum number of colors needed in properly edge-colored complete graphs to guarantee the relevant spanning-tree coverage. The latest report proposes an all-size formula but explicitly leaves that formula conjectural.

October 2026 development

Dawkins, Nappo, Tong, and Zimbizi establish a general lower bound, determine exact values for 3≤n≤123 \le n \le 12, and conjecture that the lower bound is sharp for every n≥3n \ge 3. This is substantive partial progress, not a resolution of the all-nn conjecture.

Current status (as of October 2026): The general lower bound and exact cases 3≤n≤123 \le n \le 12 are reported, while sharpness for all n≥3n \ge 3 remains open.

Sources

Solutions 0

No solutions have been posted yet.