Talk:Fractional coloring

Importance

This page should mention why (or if) this problem is important, perhaps with some applications. —Preceding unsigned comment added by 71.112.21.170 (talk) 06:25, 29 November 2008 (UTC)

Values

Is the fractional chromatic number of a finite graph always rational? Is every real number ≥1 the fractional chromatic number of a locally finite infinite graph? I guess this is well known; if it is, we should mention it. --Aleph4 (talk) 13:39, 24 January 2010 (UTC)

The fractional chromatic number of a finite graph is always rational, since the optimum value of an LP with integer coefficients is rational. — Miym (talk) 16:21, 24 January 2010 (UTC)

I see, thanks. Does this mean that the limit in the definition is actually achieved for some finite b, possibly with (effective but infeasible) bound like $b\leq 2^{2^{|V|}}$? --Aleph4 (talk) 19:13, 24 January 2010 (UTC)

Yes, for each G there always exists a finite b such that $b\chi _{f}(G)=\chi _{b}(G)$. To find such a b, "simply" solve the LP, and find a b such that $bx_{I}$ is integral for each I. Then you can also easily construct a b-fold colouring using $b\chi _{f}(G)$ colours: For example, if I is the first independent set, then we add the colours $1,2,...,bx_{I}$ to each node in I. And if J is the second independent set, we add the colours $bx_{I}+1,bx_{I}+2,bx_{I}+bx_{J}$ to each node in J, etc. In total, we assign (at least) b colours to each node, we use $b\chi _{f}(G)$ colours in total, and adjacent nodes have disjoint sets of colours. (The article should explain this equivalence much better than it currently does, please improve it if you have time and energy.) — Miym (talk) 21:23, 24 January 2010 (UTC)