The problem is such that a 2 vertices which are connected by an arc, must have different colours.
Is the following a valid ILP formulation?
$$ \min\sum_{i=1}^{n} x_i $$ $$ A^Tx = 2 $$ $$ x_i \in \{0, 1\} \quad \forall i \in \{1, \ldots, n\} $$
Where $A$ is the incidence matrix such that $a_{v,e} = 1$ if $v$ is incident to $e$.
By taking the transpose, in my interpretation, this means that for each edge (row of $A^T$) the vertices incident to such edge must be different colours.
$x_i$ = 1 if colour i is used in graph, and $0$ otherise. The number of vertices is $n$. (max number of colours is $n$).
Is this solution valid? If not can it be fixed by adding constraints or is my whole approach with the incidence matrix incorrect?
The system $A^{\mathsf T}\mathbf x = \mathbf 2$ has $m$ rows, one for each edge. The equation corresponding to a particular edge $e$ is: $$\sum_{i=1}^n A_{i,e} x_i = 2.$$ If edge $e$ connects vertices $i$ and $j$, we get $x_i + x_j = 2$. The only way to satisfy this equation is to set $x_i = x_j = 1$. So the optimal solution for this LP will set $x_i = 0$ if $i$ is an isolated vertex, and $x_i = 1$ otherwise; the result will tell us the number of vertices with at least one neighbor, which is not at all what we wanted.
This is not surprising, because variables $x_1, x_2, \dots, x_n$ don't give us any way to encode an actual coloring of the graph. Consider instead having variables $(x_{i,j})_{i,j \in [n]}$; each $x_{i,j}$ is a binary variable telling us whether vertex $i$ is given color $j$.
We can now encode the proper vertex coloring constraint with the following setup:
Color $j$ is used if and only if $x_{1,j} + \dots + x_{n,j} \ge 1$. If we add the constraint $n y_j \ge x_{1,j} + \dots + x_{n,j}$, where $y_j \in \{0,1\}$, then a single vertex getting color $j$ forces $y_j=1$. Now we can minimize $\sum_{j=1}^n y_j$ to minimize the number of colors.