The induced-matching bound for connected graphs beyond C52C_5^2 and K3,3+K_{3,3}^+

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.

Sources & referencesView supporting material

Primary source

Felix Joos, “Induced Matchings in Graphs of Maximum Degree 4”, arXiv:1407.8336 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.