Asymptotically optimal degree balance in regular graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.