On the fractional chromatic number and the lexicographic product of graphs

AbstractFor graphs G and H let G[H] be their lexicographic product and let χƒ(G) = inf{χ(G[Kn])/n | n = 1, 2, …} be the fractional chromatic number of G. For n ⩾ 1 set Gn = {G|χ(G[Kn]) = nχ(G)}. Then limn→∞ Gn = {G|χƒ(G) = χ(G)}. Moreover, we prove that for any n ⩾ 2 the class Gn forms a proper subclass of Gn−1. As a by-product we show that if G is a χ∗-extremal, vertex transitive graph on χ(G)α(G)−1 vertices, then for any graph H we have χ(G[H]) = χ(G)χ(H) − ⌊χ(H)/α(G)⌋