the following two cases. If $X$ is a subset of $\{X_1, X_2\}$, let $A=X \cup \{Y_6,Y_7\}$. If $X = \{X_2,X_3\}$, let $A= \{X_2,X_3,Y_4\}$.

Notice that there is no near-bipartite decomposition of $J$ with $\{X_1,X_2,X_3\} \subseteq A$. Combined with the above lemma, this gives an idea of how this will be used later. The vertices $X_1$, $X_2$ and $X_3$ will represent literals in a clause of an instance of [$3$-Sat]{} and membership of $A$ will indicate that a literal is false: thus $A$ can be extended to a near-bipartite decomposition except when every literal is false. (In [@MS16], a weaker result was shown: one can always find a $3$-colouring of $J$ such that members of a chosen *proper* subset of $\{X_1, X_2, X_3\}$ belong to the same class and excluded members do not belong to that class.)

Let $\phi$ be an instance of [$3$-Sat]{} with $m$ clauses $C_1, \ldots, C_m$ and $n$ variables $v_1,\ldots,v_n$. We may assume that each clause has three distinct literals. For a clause $C_k$ in $\phi$, we describe a *clause graph* ${\mathcal C}^k$, illustrated within Figure \[fig:hphi\]. We think of ${\mathcal C}^k$ as an array of $n+5m+1$ rows and eight columns. In each row except the last, 