Clique-Width Boundedness for Five Open Pairs

Open Cases: Clique-Width Classification for $(H_1,H_2)$-Free Graphs · arXiv:1811.12252

arXiv Problem medium confidence— first stated 2019-09-03

Authors: Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron

Status open medium confidence

The paper (arXiv:1811.12252) reduces the number of open pairs $(H_1,H_2)$ for clique-width boundedness to five. A 2023 follow-up by Dabrowski, Masařík, Novotná, Paulusma, and Rzążewski (arXiv:2006.03578, Journal of Graph Theory 2023) initiates a systematic study via atoms of hereditary graph classes and leaves 18 atom cases open, but its relationship to the specific five pairs from 1811.12252 could not be confirmed without the full text. No paper definitively resolving all five open pairs was found in the indexed literature.

Cited literature (1)

partial Clique-width: Harnessing the power of atoms (2023)

Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski · Journal of Graph Theory · arXiv:2006.03578 · doi:10.1002/jgt.23000

Initiates a systematic study of clique-width boundedness of atoms of hereditary graph classes, settling boundedness for $(H_1,H_2)$-free atoms in all but 18 cases; its overlap with the five open pairs from 1811.12252 could not be verified from the abstract alone.

Reviewer notes. The five remaining open pairs are not listed in the abstract of 1811.12252. The 2023 atoms paper (2006.03578) is the strongest candidate for partial progress but could not be confirmed as resolving any of the five specific pairs without full-text access. Confidence is medium rather than high because the conjecture is old enough (2019) that absence of a clear resolution is somewhat suspicious for an active research area.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Determine, for each of the five remaining pairs $(H_1, H_2)$, whether the class of $(H_1, H_2)$-free graphs has bounded or unbounded clique-width.

Context

The paper continues a project [4,8,11,12,14,15] classifying the boundedness of clique-width of $(H_1,H_2)$-free graph classes. By showing that (gem, $P_1+2P_2$)-free graphs have unbounded clique-width, the authors reduce the number of open pairs from six to five.

Notes. Not a formally labelled problem environment; inferred from the paper's statement that five open cases for clique-width boundedness remain after their contribution. PDF source.

Source paper

Graph Isomorphism for $(H_1,H_2)$-free Graphs: An Almost Complete Dichotomy
Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron · 2019-09-03
https://arxiv.org/abs/1811.12252 PDF source