What objective function I should consider?

Question

Given an undirected graph $G=(V,E), the Vertex Coloring Problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. A possible model for VCP is look like the following:

first we define, binary variables $ x_{i,k} = 1 $ if vertex $i$ is assigned to color $k$, and otherwise 0. And binary variable $y_k=1$ indicates that color $k$ has been used, and otherwise 0.

\begin{array}{rlc}{\textstyle\text{minimize}}\hspace{1em}&\sum_{k=1}^{K_{\text{max}}}y_k&\\[3pt]{\textstyle\text{subject to}}\hspace{1em}&\sum_{k=1}^{K_{\text{max}}}x_{ik}=1\hspace{1em}&\forall i\in V\\[3pt]&x_{ik}+x_{jk}\leq y_k\hspace{1em}&\forall\{i,j\}\in E;k=1,\dots,K_{\text{max}}\\[3pt]&x_{ik}\in\{0,1\}&\forall i\in V;k=1,\dots,K_{\text{max}}\\[3pt]&y_k\in\{0,1\}&k=1,\dots,K_{\text{max}}\end{array}

The first constraint ensures that exactly one color is assigned to each vertex. The second constraint imposes different colors to the endpoits of any edge ${i,j}$ , vertices $i$ and $j$, in other words, forbidding from having the same color simultaneously.

I'm trying to formulate this problem in the other way, if we directly assign each vertex a color (i.e. define an integer variable $ x_i \forall i \in [1,|V|]$ then we need to ensure that adjacent neighbors are assigned different integers (i.e. $ x_i\neq x_j \forall i\neq j$ such that $i$ is neoghbor of $j$ ). We can write these constraints as follows:

First defining a binary variable $\delta_{i,j}=1$ if $ x_i\neq x_j $, and 0 otherwise. So $ x_i\neq x_j \forall i\neq j \in E$ ) we consider these constraints:

$x_i-x_j \ge 1+|V|\delta_{i,j} \forall i,j \in E$

$x_i-x_j \le -1+|V| (1-\delta_{i,j}) \forall i,j \in E$

My question: I don't know what objective function I have to consider with this formulation.

Answer 1

Add a continuous variable $z$ together with the constraints $z \ge x_i$ for all $i\in V$ and minimize $z$. That will induce the solver to use the lowest numbered colors (i.e., $\lbrace 1,\dots, z\rbrace$), and $z$ will be the number of colors used.

Answer 2

You want to minimize the number $\chi$ of colors used. You can do this via bisection search for $\chi\in\{1,\dots,|V|\}$ by solving a feasibility problem (no objective) at each step. For each fixed value of $\chi=\hat{\chi}$ during the search, limit the domain of each $x_i$ to $\{1,\dots,\hat{\chi}\}$. If the problem is feasible for $\hat{\chi}$, it is feasible for all larger values of $\chi$. Conversely, if the problem is infeasible for $\hat{\chi}$, it is infeasible for all smaller values of $\chi$. Bisection search will terminate in $O(\log_2 |V|)$ steps.