Output-polynomial enumeration for -free incomparability graphs
Output-polynomial enumeration for -free incomparability graphs
Let be a graph. It is co-bipartite if its vertex set can be partitioned into two cliques, and let denote the problem of enumerating all minimal dominating sets of a graph.
The co-bipartite forbidden-subgraph conjecture. For any co-bipartite , there is an output-polynomial time algorithm for in -free incomparability graphs.
This is described as a bold generalization of the preceding conjecture. The case is known for incomparability graphs because -free incomparability graphs are interval graphs, but the conjecture for arbitrary co-bipartite remains open.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.