A Fractional Analogue of Brooks' Theorem

Original · EN

Let Δ(G) be the maximum degree of a graph G. Brooks' theorem states that the only connected graphs with chromatic number χ(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 χf(G) is at least Δ(G). These graphs are complete graphs, odd cycles, C²₈, C₅ K₂, and graphs whose clique number ω(G) equals the maximum degree Δ(G). Among the two sporadic graphs, the graph C²₈ is the square graph of cycle C₈ while the other graph C₅ K₂ is the strong product of C₅ and K₂. 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 χf(G)≤ Δ(G)- 2/67.