Dom-Enum polynomial in Sₜ-free incomparability graphs
Conjecture 7.1 · arXiv:2004.07214
Status open medium confidence
Conjecture 7.1 from arXiv:2004.07214 asks for an output-polynomial time algorithm for Dom-Enum in incomparability graphs of $S_t$-free posets, as the natural counterpart to the paper's Corollary 5.3 (which covers comparability graphs of $S_t$-free posets) and Theorem 1.1 (incomparability graphs of bounded-dimension posets). The paper, originally posted in April 2020 and published in Discrete Mathematics in 2025, leaves this as an open problem. No follow-up paper resolving the conjecture was found in the indexed literature; a related 2025 WADS paper (chordal bipartite graphs) cites the source paper but addresses a different graph class.
Reviewer notes. The conjecture has been open since April 2020. The paper proves the comparability-graph analogue (Corollary 5.3) and the bounded-dimension case for incomparability graphs (Theorem 1.1), but the S_t-free incomparability case resists the same techniques because comparability graphs of S_t-free posets are not of bounded LMIM-width. A WADS 2025 paper on chordal bipartite graphs cites arXiv:2004.07214 but does not address this conjecture. Confidence is medium rather than high because the arXiv preprint is from 2020 (~6 years old), making the absence of a resolution somewhat surprising.
Context
The algorithm of Corollary 5.3 already covers all comparability graphs of $S_{t}$-free posets. The paper asks what can be said about Dom-Enum in $H$-free incomparability graphs; since co-bipartite graphs are incomparability graphs, the question is only interesting for co-bipartite $H$. This conjecture is proposed as the natural counterpart of Theorem 1.2 for the $S_t$-free setting.
Also stated in
Source paper
Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
Marthe Bonamy, Oscar Defrain, Piotr Micek, Lhouari Nourine · 2025-11-26
https://arxiv.org/abs/2004.07214