The forbidden-subgraph characterization conjecture for dominating induced matchings

Let MM be a finite set of graphs. Let S\cal S be the class of graphs whose connected components are graphs Si,j,kS_{i,j,k}. An MM-free graph is a graph containing no induced subgraph isomorphic to a graph in MM.

Forbidden-subgraph characterization conjecture. Unless P=NPP=NP, the dominating induced matching problem is polynomial-time solvable in the class of MM-free graphs if and only if MM contains a graph from S\cal S.

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

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.