Please look at my approach to the following problem
$y_{jk}$ could be seen as entries in a 0/1 n$\times$n matrix, in which, by the first constraint, there is exactly 1 entry of value "1" in each row, and, by the second constraint, no columns has 2 such entries. But then there two constraints imply that the matrix has 1 "1" in each row and column, and zero everywhere else. This in turn implies that all the $x_i$'s must be 1, in order to satisfies the third constraint. So I don't see how this is a linear program and how it's corresponding to some parameter of a graph.
=================================================================
Edit: an answer below by Kuifje (https://math.stackexchange.com/a/3072279/120141) points out that the program actually looks for the chromatic number of the graph G. I'd like to ask for some more clarification and answers to some further questions below:
The graph G is obviously properly colored if each vertex has a different color, i.e. we use $n$ colors in total. So we can think of $y_{jk}$ as the choice of color for vertex $j$, amongst the $n$ possible colors. This makes sense of the first and second constraints.
However I still have some questions:
(1) How should I interpret the third constraint?
(2) How should I interpret the variables $x_i$'s?
(3) Could it be that the number $\sum x_i$ is also the list-chromatic number of G?
(4) If we follow my original analysis, since all $x_i$'s are always 1, $min \sum x_i$ would always be $n$. I still don't see where I went wrong with this argument.
The linear program gives you the chromatic number of the graph (the minimum number of colors needed to color every node such that no two adjacent nodes share the same color).
The first constraint forces each node to have a color.
The second one makes sur two adjacent nodes have different colors.
The third one activates a binary variable that counts if color $k$ is used.
The objective function minimizes these variables, that is, the number of total colors used.
EDIT : Follow up on the extra questions :
1) Interpretation of the third constraint ($ y_{jk} \le x_k $) : when color $k$ is given to node $j$, $y_{jk}$ takes value $1$, which requires $x_k$ to also take value $1$ : in other words $x_k$ is a counter that is activated when color $k$ is used.
2) $x_k$ is a counter that is activated when color $k$ is used.
3) I don't think so : here, it is assumed that a node can receive any given color among $\{1,...,n\}$
4) All $x_i$s are not always $1$. For example, if the graphe is a path with $3$ nodes, the first and last can take color $1$, the second can take color $2$, and color $3$ is never used (so $x_3=0$).