A Catlin-type Theorem for Graph Partitioning Avoiding Prescribed Subgraphs
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 $Δ(H)$, then $H$ has a vertex $Δ(H)$-coloring such that one of the color classes is a maximum independent set. Let $G$ be a connected graph of order at least $2$. A $G$-free $k$-coloring of a graph $H$ is a partition of the vertex set of $H$ into $V_1,\ldots,V_k$ such that $H[V_i]$, the subgraph induced on $V_i$, does not contain any subgraph isomorphic to $G$. As a generalization of Catlin's theorem we show that a graph $H$ has a $G$-free $\lceil{Δ(H)\over δ(G)}\rceil$-coloring for which one of the color classes is a maximum $G$-free subset of $V(H)$ if $H$ satisfies the following conditions; (1) $H$ is not isomorphic to $G$ if $G$ is regular, (2) $H$ is not isomorphic to $K_{kδ(G)+1}$ if $G \simeq K_{δ(G)+1}$, and (3) $H$ is not an odd cycle if $G$ is isomorphic to $K_2$. Indeed, we show even more, by proving that if $G_1,\ldots,G_k$ are connected graphs with minimum degrees $d_1,\ldots,d_k$, respectively, and $Δ(H)=\sum_{i=1}^{k}d_k$, then there is a partition of vertices of $H$ to $V_1,\ldots,V_k$ such that each $H[V_i]$ is $G_i$-free and moreover one of $V_i$s can be chosen in a way that $H[V_i]$ is a maximum $G_i$-free subset of $V(H)$ except either $k=1$ and $H$ is isomorphic to $G_1$, each $G_i$ is isomorphic to $K_{d_i+1}$ and $H$ is not isomorphic to $K_{Δ(H)+1}$, or each $G_i$ is isomorphic to $K_{2}$ and $H$ is not an odd cycle.