Output-polynomial enumeration for -free incomparability graphs
Let be a positive integer, let be the disjoint union of two copies of the clique , and let denote the problem of enumerating all minimal dominating sets of a graph.
The -free incomparability conjecture. For every , there is an output-polynomial time algorithm for in -free incomparability graphs.
This is presented as a directly easier conjecture than the corresponding statement for incomparability graphs of -free posets. It holds for and is known for , while the case 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
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.