I'm searching for a reference to a particular alternate definition of the fractional chromatic number of graphs.

Let me review the most common definition and basic properties first.

Let $ G $ be a (finite simple) graph. For any natural number $ n $, we define the multi-chromatic number $ \chi_n(G) $ as the least $ m $ such that you can have a multi-coloring function $ c $ mapping the vertices of $ G $ to $ n $ element subsets of $ [m] $ such that the color of any two adjacent vertices have no intersection. We then define the fractional chromatic number of the graph as $ \chi^*(G) = \inf_n \chi_n(G)/n $.

It can be proved that this infimum is equal to the limit and equal to $ \chi_k(G)/k $ for some number $ k $, and so it is always rational as well. The fractional chromatic number of a graph is bounded from above by its chromatic number $ \chi(G) $ and from below by its clique number $ \omega(G) $.

Now the alternate definition I'm asking for.

I define the multi-chromatic number as $ \chi_n(G) = \chi(GK_n) $. Here $ GK_n $ is the graph you get by replacing each vertex of $ G $ by an $ n $-clique and each edge by $ n^2 $ edges linking each vertex from one corresponding clique to the other. I then define the fractional chromatic number the same as above.

(I use the notation $ GK_n $ because the graph is the lexicographical product of $ G $ and $ K_n $.)

It is easy to prove that this definition gives the same value for the multi-chromatic number as the usual definition. Indeed, if you have a coloring of $ GK_n $ with $ m $ colors, you get a natural $ n $-multi-coloring of $ G $ with $ m $ colors by defining the color of each vertex to the set of colors of the corresponding vertices in $ GK_n $, and this construction can be reversed as well.

While it's easy to see that the definition is equivalent, I'd like a reference from an existing book or article that gives this definition. This would show that people other than me find this definition natural.

I know there are other alternate definitions of the fractional chromatic number, namely there is one that gives it as the solution of a particular linear program, one using Kneser graphs, or one that uses graph powers. I'm not interested in those for this question.

I have searched in Pavol Hell, Jaroslav Nesetril, Graphs and Homomorphisms, and in Edward R. Scheinerman, Daniel H. Ullman, Fractional Graph Theory. Both of these talk about the fractional chromatic number in detail, but they don't give the definition I need.

  • 1
    $\begingroup$ A friend of mine is working on the same area. However, he is not a mathoverflower. You may e-mail him at his yahoo email: iradmusa (it is his surname). I hope he knows about what you are looking for. $\endgroup$ – Amir Asghari Jun 3 '13 at 7:09

This result, or something that sounds very similar, is in the paper "On the fractional chromatic number and the lexicographic product of graphs", Sandi Klavẑar (1998). Within that paper, a few references are cited for similar results as well.

  • $\begingroup$ Thank you. This article definitely gives the definition I asked for. $\endgroup$ – Zsbán Ambrus Jan 6 '14 at 14:19

Wilfried Imrich, Sandi Klavžar, Product Graphs, Structure and Recognition gives this as theorem 8.38 on page 268 as well. I should have looked in this book earlier, but now Dan Stahlke's answer made me check it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.