Dom-Enum in co-bipartite H-free incomparability graphs
Conjecture 7.3 · arXiv:2004.07214
Status open medium confidence
No paper resolving Conjecture 7.3 was found. The closest related follow-up is a 2025 WADS paper (arXiv:2502.14611, Castelo–Defrain–Gomes) giving polynomial-delay algorithms for minimal dominating sets in chordal bipartite graphs, which cites 2004.07214 but does not address the co-bipartite H-free incomparability setting of Conjecture 7.3. The broader problem of Dom-Enum in H-free incomparability graphs for co-bipartite H remains open, with the conjecture having been present in the arXiv preprint since April 2020.
Reviewer notes. Confidence is medium rather than high because the arXiv preprint has been available since April 2020 (over five years), making the absence of follow-up more notable. A related WADS 2025 paper (arXiv:2502.14611, Castelo–Defrain–Gomes) proves polynomial delay for chordal bipartite graphs and cites the source paper, but does not address Conjecture 7.3. The conjecture is the broadest of three open problems in the concluding section, subsuming Conjecture 7.2, and the paper notes that the incomparability condition may not even be necessary. Source paper published in Discrete Mathematics (ScienceDirect, November 2025, doi link found at sciencedirect.com/science/article/abs/pii/S0012365X25005126).
Context
This is the broadest of the three conjectures in the concluding section, subsuming Conjecture 7.2. The authors note there is no blatant reason why the incomparability condition should be necessary, leaving open whether the result might hold for all $H$-free graphs with co-bipartite $H$.
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