Cliquewidth of triangle, S₁,₂,₃-free graphs
Open Question: (triangle, S1,2,3)-free graphs cliquewidth · arXiv:2001.01607
Status open high confidence
The question of whether (triangle, $S_{1,2,3}$)-free graphs have bounded cliquewidth remains open as of 2026. Bounded cliquewidth has been established for the smaller class (triangle, $S_{1,2,2}$)-free graphs (arXiv:1608.01820) and for (triangle, $H$)-free graphs when $H \in \{P_6, S_{1,1,3}\}$, but the $S_{1,2,3}$ case is explicitly identified as open in the source paper. No follow-up paper resolving this question was found in a targeted web search across arXiv and the broader literature.
Reviewer notes. No follow-up resolving this open question was found. The closely related settled cases are: (triangle, S_{1,2,2})-free graphs (bounded cliquewidth, arXiv:1608.01820) and (triangle, P_6)-free and (triangle, S_{1,1,3})-free graphs. The S_{1,2,3} case sits just outside the resolved boundary and is the next open case in the hierarchy. The internal reference arXiv:2203.06775 was not verified to be relevant to this conjecture.
Context
Bounded cliquewidth is known for (triangle, $S_{1,2,2}$)-free graphs and for (triangle, $H$)-free graphs when $H$ is contained in a graph from $H_B = \{P_6, S_{1,1,3}\}$. The status of $S_{1,2,3}$ is explicitly open; the authors refer to [16] for further open problems of the same flavour.
Notes. PDF source — math notation reconstructed; stated in the 'Open questions' section.
Source paper
(Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 2 : bounds on treewidth
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon · 2020-10-27
https://arxiv.org/abs/2001.01607
PDF source