Equal weighted colors in fractional colorings

100 Views Asked by At

I'm not sure if this is true, but does there always exist a fractional coloring of a graph $G$ that has a total weighting equal to the fractional chromatic number of $G$ such that the fractional coloring uses colors that are all equal in weight?

For example, the fractional chromatic number of the 5-cycle graph is $\frac{5}{2}$, and this can be attained by only using colors all of which that have a weight of $\frac{1}{2}$. But is this the case for any graph? If so, which textbook, paper etc. claims and proves this?

1

There are 1 best solutions below

3
On BEST ANSWER

In one possible definition of fractional coloring, to each independent set $I \subseteq V(G)$ we assign a weight $x_I$, such that at each vertex $v$ the total weight is at least $1$: $$\sum_{I\, :\, v \in I} x_I \ge 1.$$ The idea is that if $x_I$ is nonzero, then there is a color that is put on all the vertices of $I$, but only with weight $x_I$. We try to minimize the total weight of all colors: the sum of $x_I$ over all $I$.

If we take this approach, then it may not be possible to make all nonzero $x_I$ equal. Consider the following graph:

wheel-5

Here, the only independent set containing the central vertex $0$ is the set $\{0\}$, so we must have $x_{\{0\}} = 1$. But if we try to use only weight $1$ for coloring the remaining vertices $\{1,2,3,4,5\}$ then we end up finding the ordinary chromatic number, $4$. The fractional chromatic number of $\frac72$ can only be obtained by setting $x_{\{1,3\}} = x_{\{3,5\}} = x_{\{2,5\}} = x_{\{2,4\}} = x_{\{1,4\}} = \frac12$.


However, we can get around this problem if we are allowed to have "functionally identical" colors. If that's the case, then we find a common denominator, $q$, of all the $x_I$. (We know the $x_I$ are all rational because any linear program with rational coefficients has a rational optimal solution.) Now, if the solution above has $x_I = \frac{p_I}{q}$, then instead of having a single color on the vertices in $I$ with weight $x_I$, we have $p_I$ different colors on the vertices in $I$, each with weight $\frac{1}{q}$.

This does not change the total weight of all the colors; however, after we do this for all $I$, every color used has weight $\frac1q$, and so we get what we want.