ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a connected graph with maximum degree Δ≥3 \Delta\geq 3. Let C52C_5^2 be the graph obtained from a 55-cycle by replacing its vertices with independent sets of order 22, and let K3,3+K_{3,3}^+ be the graph obtained from K3,3K_{3,3} by subdividing exactly one edge once. Write n(G)n(G) for the number of vertices, and let us(G) u_s(G) denote the maximum size of an induced matching in GG. The induced-matching bound conjecture. If G∉{C52,K3,3+}G\notin\{C_5^2,K_{3,3}^+\}, then

νs(G)≥1(⌈Δ2⌉+1)(⌊Δ2⌋+1)n(G).\nu_s(G) \geq \frac{1}{\left(\left\lceil\frac{\Delta}{2}\right\rceil+1\right)\left(\left\lfloor\frac{\Delta}{2}\right\rfloor+1\right)}n(G).

The conjecture is motivated by a theorem giving this bound for sufficiently large maximum degree and by the exceptional graphs C52C_5^2 and K3,3+K_{3,3}^+, which show that the corresponding theorem cannot extend unchanged to maximum degree three or four. Its validity for all connected graphs satisfying the stated hypotheses remains 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 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.