ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let G=(V,E)G=(V,E) be a connected graph, and let m=∣E∣m=|E| be its number of edges. An edge-irregulator of GG is a set S⊆ES\subseteq E such that G−SG-S is locally irregular, meaning that every edge of G−SG-S joins vertices of different degrees; write Ie(G){\rm I}_e(G) for the minimum possible size of an edge-irregulator. Edge-irregularity deletion conjecture. There is an absolute constant c≥1c\geq 1 such that, for every connected graph GG with mm edges,

Ie(G)≤13m+c.{\rm I}_e(G)\leq \frac{1}{3}m+c.

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 K2K_2 and C4C_4 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.