Jump to content

Talk:Fractional coloring

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Importance

[edit]

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)[reply]

Values

[edit]

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)[reply]

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)[reply]

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 ? --Aleph4 (talk) 19:13, 24 January 2010 (UTC)[reply]

Yes, for each G there always exists a finite b such that . To find such a b, "simply" solve the LP, and find a b such that is integral for each I. Then you can also easily construct a b-fold colouring using colours: For example, if I is the first independent set, then we add the colours to each node in I. And if J is the second independent set, we add the colours to each node in J, etc. In total, we assign (at least) b colours to each node, we use 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)[reply]