Recognizing Graphs Admitting a Triangle-Free Thin Graph of Treewidth at Most Two Is NP-Complete

We settle the recognition problem for graphs that admit a thick model whose thin graph is triangle-free and has treewidth at most two. Neither the thin graph nor the fiber map is part of the input, and an edge of the thin graph need not be realized by an edge between its two fibers in the input graph. Dyer and Müller left open whether this class is polynomial-time recognizable; we prove that recognition is NP-complete by a Karp reduction from 2-colorability of 3-uniform hypergraphs. The reduction uses two large cliques joined by a matching and a three-vertex path gadget for each hyperedge. Triangle-freeness forces an aligned split of the cliques, which encodes a valid coloring, while a coloring yields an explicit bipartite quotient of treewidth two. The reduction supplies the hardness side of a fixed-treewidth dichotomy. Together with the thick-forest algorithm, it yields polynomial-time recognition for each fixed k ∈ {0,1} and NP-completeness for every fixed k ≥ 2 for both triangle-free and bipartite thin graphs. NP-completeness also persists when the allowed thin graph is required to be bipartite, have treewidth at most two, and contain a dominating edge; every such thin graph is chordal bipartite. In contrast, for every fixed r, the main recognition problem is polynomial-time solvable on input graphs of clique number at most r; in particular it is polynomial on triangle-free inputs.