1
$\begingroup$

Please look at my approach to the following problem

enter image description here

$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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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$).

$\endgroup$
6
  • $\begingroup$ Where did my analysis go wrong? Following that line of reason, since all $x_i$'s are always 1's, min $\sum x_i$ would always be $n$. $\endgroup$ Commented Jan 13, 2019 at 17:43
  • $\begingroup$ I think I might have an inkling of how to interpret your answer: 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. $\endgroup$ Commented Jan 13, 2019 at 20:05
  • $\begingroup$ I still have some questions nonetheless: (1) how should I interpret the third constraint?, (2) how should I interpret the variables $x_i$?, (3) could it be that the number $\sum x_i$ is also the list-chromatic number of G?, (4) i still don't see how my analysis as mentioned above is wrong? $\endgroup$ Commented Jan 13, 2019 at 20:05
  • 1
    $\begingroup$ I have edited my answer to take into account your extra questions. $\endgroup$ Commented Jan 14, 2019 at 8:57
  • $\begingroup$ Thanks! I think i found where it went wrong! In setting up the n$\times$n matrix, i forgot that not all vertices are adjacent to all other vertices, so if i want to go that way i’d need more specifications for the matrix. Or, to look at it another way, that matrix would be valid for the trivial case of the complete graph $K_n$. $\endgroup$ Commented Jan 15, 2019 at 12:49

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.