The beauty of QAP is that it is NP-Complete. Thus, the 3-coloring problem reduces to QAP. In fact, any problem in NP can be represented using QAP constraints.
More practically, all that is required is an arithmetic encoding of a graph and a coloring. Then, the rest of the work is to design arithmetic constraints such as the ones you saw in the write-up that encode the 3-coloring requirements.
For example, I can represent graphs as node labels as elements $1, 2, 3, \dots$ in the field and the edge set as pairs $(1,4), (1,6), \dots$. For the coloring, you can choose the numbers $1,2,3$.
Then, the QAP input-witness pair are simply those elements laid out in a long vector (to encode a tuple, you can just designate the left and right inputs are adjacent).
$$(1,t_{1,l}, t_{1,r}, t_{2,l}, t_{2,r}\dots, t_{m, l}, t_{m, r};c_{1}, c_{2},\dots, c_{n}, p^{-1})$$
where $1$ will be a public helper element (useful when you need constants), $t$'s are public instance inputs representing the graph (where the i'th edge (a,b) is encoded as $t_{i, l}=a, t_{i,r}=b$) and the coloring $c$'s are the private witness inputs.
There's an additional witness input $p^{-1}$, which we will use later. Here, I’m omitting all of the intermediate variables which also must be included in the witness, but it suffices just to extend the witness to add them. I suggest reading the intuition below and then coming back to this minor issue. Now the tricky part is how to encode the witness validity checks and coloring constraints.
- First, you have to verify that all the $c_i\in\{1,2,3\}$. You can do this by encoding the constraint $(c_i-1)(c_i-2)(c_i-3)=0$. Notice the degree of this constraint is three. I'll leave it up to you to figure out how you can encode that in multiple QAP constraints; hint, requires some intermediate variables / inputs.
- Then, you need to encode the coloring constraint. This is a little more complicated. You need to encode the constraint: For every tuple $(a,b)$, $c_a-c_b\neq 0$... This requires lookup constraints to match corresponding colors to indices in the tuple... I suggest you ask a separate question on how to encode lookup constraints (as it's more complicated), but after the lookup constraints. You should end up with intermediate variables which encode the following vector:
$$c_{t_{1,l}}, c_{t_{2,l}}, ..., c_{t_{m,l}}, c_{t_{m,l}}$$
Then, you can produce intermediate variables that encode:
$$c_{t_{1,l}}-c_{t_{2,l}}, ..., c_{t_{m,l}}-c_{t_{m,l}}$$
Then, you can obtain their product:
$$p := \prod_{i\leq m}(c_{t_{i,l}}-c_{t_{i,l}})$$
by using a linear number of intermediate constraints. Now all you have to check is that $p\neq 0$. To do so, you can add a witness input $p^{-1}$ and check the constraint $p\cdot p^{-1} = 1$. The reason for this constraint is that 0 does not have an inverse in the field.
