Output-polynomial enumeration for HH-free incomparability graphs

Let HH be a graph. It is co-bipartite if its vertex set can be partitioned into two cliques, and let \textscDomEnum\textsc{Dom-Enum} denote the problem of enumerating all minimal dominating sets of a graph.

The co-bipartite forbidden-subgraph conjecture. For any co-bipartite HH, there is an output-polynomial time algorithm for \textscDomEnum\textsc{Dom-Enum} in HH-free incomparability graphs.

This is described as a bold generalization of the preceding conjecture. The case H=C4H=C_4 is known for incomparability graphs because C4C_4-free incomparability graphs are interval graphs, but the conjecture for arbitrary co-bipartite HH 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

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.