A Catlin-type Theorem for Graph Partitioning Avoiding Prescribed Subgraphs

Abstract

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)$-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,\dots ,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 \frac{\Delta (H)}{\delta (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\delta (G)+1}$ if $G\simeq K_{\delta (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,\dots ,G_k$ are connected graphs with minimum degrees $d_1,\dots ,d_k$, respectively, and $\Delta (H)={\sum }_{i=1}^k{d}_k$, then there is a partition of vertices of $H$ to $V_1,\dots ,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_{\Delta (H)+1}$, or each $G_i$ is isomorphic to $K_2$ and $H$ is not an odd cycle.

8 pages