Output-polynomial enumeration for 2Kp2K_p-free incomparability graphs

Let pp be a positive integer, let 2Kp2K_p be the disjoint union of two copies of the clique KpK_p, and let \textscDomEnum\textsc{Dom-Enum} denote the problem of enumerating all minimal dominating sets of a graph.

The 2Kp2K_p-free incomparability conjecture. For every pp, there is an output-polynomial time algorithm for \textscDomEnum\textsc{Dom-Enum} in 2Kp2K_p-free incomparability graphs.

This is presented as a directly easier conjecture than the corresponding statement for incomparability graphs of StS_t-free posets. It holds for p=1p=1 and is known for p=2p=2, while the case p=3p=3 is widely open without the incomparability assumption.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, Oscar Defrain, Piotr Micek and Lhouari Nourine, “Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets”, arXiv:2004.07214 (2025).

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.