A Fractional Analogue of Brooks' Theorem
A Fractional Analogue of Brooks' Theorem
Let $\Delta(G)$ be the maximum degree of a graph G. Brooks' theorem states that the only connected graphs with chromatic number $\chi(G)=\Delta(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 …