The induced-matching bound for connected graphs beyond and
The induced-matching bound for connected graphs beyond and
Let be a connected graph with maximum degree . Let be the graph obtained from a -cycle by replacing its vertices with independent sets of order , and let be the graph obtained from by subdividing exactly one edge once. Write for the number of vertices, and let denote the maximum size of an induced matching in . The induced-matching bound conjecture. If , then
The conjecture is motivated by a theorem giving this bound for sufficiently large maximum degree and by the exceptional graphs and , 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
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.