The m(G)/17m(G)/17 bound for induced matchings without C52C_5^2 components

Let GG be a graph, let m(G)m(G) denote its number of edges, and let C52C_5^2 denote the graph obtained by replacing each vertex of a 55-cycle with an independent set of order 22. An induced matching is a matching whose endpoints induce exactly the edges in the matching; write us(G) u_s(G) for the maximum size of an induced matching in GG. The m(G)/17m(G)/17 conjecture. If GG has maximum degree at most 44 and no component is isomorphic to C52C_5^2, then

νs(G)m(G)17.\nu_s(G)\geq \frac{m(G)}{17}.

The preceding theorem gives the best possible general bound with a possible C52C_5^2 component, while the source notes that no example without such a component attaining the weaker ratio m(G)/18m(G)/18 was known. The proposed bound remains open in the paper.

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.