Output-polynomial enumeration for 2Kp2K_p-free incomparability graphs

About 6 years old · traced to

Let pp be a positive integer, let 2Kp2K_p be the disjoint union of two copies of the clique KpK_p, and let \textscDom−Enum\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 \textscDom−Enum\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.

References

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.