A FRACTIONAL ANALOGUE OF BROOKS' THEOREM.

Let Δ (G) be the maximum degree of a graph G. Brooks' theorem states that the only connected graphs with chromatic number X(G) = Δ (G) + 1 are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs G such that the fractional chromatic number Xf(G) is at least Δ (G). These graphs are complete graphs, odd cycles, C²8 C5 ⊠ K2, and graphs whose clique number ω(G) equals the maximum degree Δ (G). Among the two sporadic graphs, the graph C²8 is the square graph of cycle C8, while the other graph C5 ⊠ K2 is the strong product of C5 and K2. In fact, we prove a stronger result: If a connected graph G with δ (G) ≥ 4 is not one of the graphs listed above, then we have Xf(G)≤ Δ(G) -- 2/67. [ABSTRACT FROM AUTHOR]