Asymptotically optimal degree balance in regular graphs
Let be a -regular graph of order , and let denote the number of vertices of degree in a spanning subgraph . Asymptotic degree-balance conjecture. For every there is a finite family of exceptional graphs such that every -regular graph of order not belonging to has a spanning subgraph for which, for every integer with , if and are odd integers, then
otherwise,
when is even, and
when is odd. This conjecture refines the degree-balance problem by asserting that, apart from finitely many exceptions for each , the parity obstruction is the only obstruction to attaining the bound . The source explicitly notes that even the case is open.
References
Primary source
Borut Lužar, Jakub Przybyło and Roman Soták, “Degree-balanced decompositions of cubic graphs”, arXiv:2408.16121 (2025).
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
No solutions have been posted yet.