Asymptotically optimal degree balance in regular graphs
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Borut Lužar, Jakub Przybyło and Roman Soták, “Degree-balanced decompositions of cubic graphs”, arXiv:2408.16121 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.