Deficiency bounds for complete graphs of power-of-two order

Let qZ+q\in\mathbb{Z}_+, let K2q+1+1K_{2^{q+1}+1} be the complete graph on 2q+1+12^{q+1}+1 vertices, and let wdef(G)w_{def}(G) and Wdef(G)W_{def}(G) denote the minimum and maximum, respectively, of the number of colors in a proper edge-coloring of GG having minimum deficiency.

Complete-graph deficiency conjecture. For any qZ+q\in\mathbb{Z}_+,

wdef(K2q+1+1)=Wdef(K2q+1+1)=32q.w_{def}\left(K_{2^{q+1}+1}\right)=W_{def}\left(K_{2^{q+1}+1}\right)=3\cdot2^q.

The conjecture is motivated by the inability to find a proper edge-coloring of these complete graphs with more than 32q3\cdot2^q colors having minimum deficiency. It remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Petros A. Petrosyan and Hrant H. Khachatrian, “Further results on the deficiency of graphs”, arXiv:1608.00904 (2017).

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.