A Catlin-type Theorem for Graph Partitioning Avoiding Prescribed Subgraphs

Yaser Rowshan, Ali Taherkhani

As an extension of the Brooks theorem, Catlin in 1979 showed that if $H$ is neither an odd cycle nor a complete graph with maximum degree $\Delta (H)$, then $H$ has a vertex $\Delta (H)$-color…