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
- 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.