Deficiency bounds for complete graphs of power-of-two order
Deficiency bounds for complete graphs of power-of-two order
Let , let be the complete graph on vertices, and let and denote the minimum and maximum, respectively, of the number of colors in a proper edge-coloring of having minimum deficiency.
Complete-graph deficiency conjecture. For any ,
The conjecture is motivated by the inability to find a proper edge-coloring of these complete graphs with more than 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.