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.

¡@

¡@

¡@