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

About 12 years old · traced to

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.

References

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.