The edge-irregularity deletion conjecture
Statement
Let be a connected graph, and let be its number of edges. An edge-irregulator of is a set such that is locally irregular, meaning that every edge of joins vertices of different degrees; write for the minimum possible size of an edge-irregulator. Edge-irregularity deletion conjecture. There is an absolute constant such that, for every connected graph with edges,
The conjecture is motivated by the behaviour of cycles, where deleting one edge can resolve at most three local degree conflicts, while small graphs such as and show that an additive constant is necessary. The general bound remains open in the source paper.
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.