The bound for induced matchings without components
The bound for induced matchings without components
Let be a graph, let denote its number of edges, and let denote the graph obtained by replacing each vertex of a -cycle with an independent set of order . An induced matching is a matching whose endpoints induce exactly the edges in the matching; write for the maximum size of an induced matching in . The conjecture. If has maximum degree at most and no component is isomorphic to , then
The preceding theorem gives the best possible general bound with a possible component, while the source notes that no example without such a component attaining the weaker ratio 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.