The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity holds for all directed graphs G and H. Similar bounds for the usual chromatic number seem to be much harder to obtain: It is still not known whether there exists a number n such that χ(G×H) ≥ 4 for all directed graphs G, H with χ(G) ≥ χ(H) ≥ n. In fact, we prove that for every integer n ≥ 4, there exist directed graphs G_n, H_n such that χ(G_n) = n, χ(H_n) = 4 and χ(G_n×Hⁿ) = 3.