Fractional Chromatic Numbers of Incidence Graphs

In 1993, Brualdi and Massey defined the incidence graph of G, Inc(G), to be the graph whose vertices are the set of incidences - pairs of the form (u, e) where u is a vertex of G and e is an edge of G containing u as an endpoint - and where two incidences, (u, e) and (v, f), are adjacent if (i) u = v, (ii) e = f or (iii) uv = e or uv = f. They determine the incidence chromatic number, Xi(G) = X(Inc(G)), of several classes of graphs and use this work to study the strong chromatic index of a certain bipartite graph H which is associated to G. Much work has been done in computing and bounding the incidence chromatic number of graphs. Of particular interest, in 2012, Yang defined the fractional incidence chromatic number of a graph to be Xf (Inc(G)); that is, the fractional chromatic number of the incidence graph of G. In what follows, we generalize many known bounds on the incidence chromatic number to bounds on the fractional incidence chromatic number. By providing a lower bound on the fractional incidence chromatic number which provides equality when Inc(G) is vertex transitive and giving a sufficient condition for when Inc(G) is vertex transitive, we are able to compute the fractional incidence chromatic number of several families of graphs. Further, we generalize the bounds for the union, Cartesian product and join of two graphs obtained by Sun and Shiu along with the bounds for the lexicographic and direct products of two graphs and a bound involving the star arboricity and the edge chromatic number obtained by Yang. We also show that these bounds are all tight. Given these bounds, along with another bound involving the square of a graph, we show that Xf (C3n[Kl]) = 3l for n >= 1 and l >= 2. Finally, using the Strong Perfect Graph Theorem, we show that Inc(G) is perfect precisely when G has circumference at most 3; that is, when a longest cycle in G has length at most 3. As a result, we compute Xf (Inc(G)) in this case. We end with a discussion on some future work.