the vertices of the dominating blocks and, in each row, either all the true vertices or all the false vertices. Thus if $B$ contains a cycle then all the vertices of the cycle belong to the same clause graph (the only edges going between distinct clause graphs are those joining true vertices to false vertices in the same row). Let $G_B$ be a subgraph of a clause graph induced by vertices of $B$. Then each true and false vertex not in the constraint graph has degree $1$ (due to the edge joining it to the dominating block), and each vertex in the dominating block has at most one neighbour with degree more than $1$ (since it only has one neighbour in the constraint graph). Thus if $G_B$ contains a cycle then it belongs to the constraint graph, contradicting how $A$ and $B$ were chosen.

($\Leftarrow$) Suppose $A$ and $B$ form a near-bipartite decomposition of $H_\phi$. Then $B$ can be decomposed into two independent sets, and these, along with $A$, can be considered a $3$-colouring. In [@MS16 Theorem 5], it is shown that if $H_\phi$ has a $3$-colouring, then $\phi$ is satisfiable.

Conclusions {#s-con}
===========

We completed the computational complexity classifications 