The forbidden-subgraph characterization conjecture for dominating induced matchings
The forbidden-subgraph characterization conjecture for dominating induced matchings
Let be a finite set of graphs. Let be the class of graphs whose connected components are graphs . An -free graph is a graph containing no induced subgraph isomorphic to a graph in .
Forbidden-subgraph characterization conjecture. Unless , the dominating induced matching problem is polynomial-time solvable in the class of -free graphs if and only if contains a graph from .
This conjecture proposes that the known necessary condition for polynomial-time solvability on finitely characterized graph classes is also sufficient. The parser marks the conjecture as disproved, although the supplied surrounding text only says that proving or disproving it is challenging; the resolution evidence should therefore be checked.
Sources & referencesView supporting material
Primary source
Alain Hertz, Vadim Lozin, Bernard Ries, Victor Zamaraev and Dominique de Werra, “Dominating induced matchings in graphs containing no long claw”, arXiv:1505.02558 (2015).
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.