A Fractional Analogue of Brooks' Theorem

Andrew D. King, Linyuan Lu, Xing Peng

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 pr…