Chi_f of product graphs
Suppose G = ( V, E ) and H = ( V', E' ) . The categorical product G x H has vertex set V x V' = { (x, x'): x \in V, x' \in V' }, in which (x, x') is adjacent to (y, y') if and only if x is adjacent to x' in G and y is adjacent to y' in H. Any fractional r-coloring f of G induces a fractional r-coloring g of G x H defined as g(I x V') = f(I)., where I is an independent set of G, and I x V' = { (x, x') : x \in I, x' \in V'}. Therefore chi_f(G x H) <= chi_f(G). Similarly, chi_f(G x H) <= chi_f(H).
Conjecture For any rational p/q, if min { chi_f(G), chi_f(H) } > p/q, then chi_f(G x H) > p/q. In other words, chi_f( G x H ) = min { chi_f(G), chi_f(H) }.
The conjecture has been proved [Zhu02] for the case that one of G, H is a Kneser graph, or a circular complete graph, or is the direct sum of such graphs.
It was proved by Claude Tardif (not appeared yet) that if min { chi_f(G), chi_f(H) } > p/q, then chi_f(G x H) > p/2q.
¡@
¡@
¡@