论文标题
用于图形分区的catlin型定理避免了规定的子图
A Catlin-type Theorem for Graph Partitioning Avoiding Prescribed Subgraphs
论文作者
论文摘要
作为Brooks定理的扩展，Catlin于1979年表明，如果$ h $既不是奇数周期，也不是最高度$δ（h）$的完整图，则$ h $具有顶点$δ（h）$ - 颜色，以便其中一种颜色类是最大独立集。令$ g $为连接的订单图，至少$ 2 $。 a $ g $ -free $ k $ - 图$ h $的颜色是$ h $的顶点$ h $的分区，$ v_1，\ ldots，v_k $，以至于$ h [v_i] $，$ h [v_i] $，对$ v_i $诱导的子级，不包含任何子图与$ g $ g $。作为对Catlin定理的概括，我们表明，图$ h $具有$ g $ - free $ \ lceil {δ（h）\ fovue uccon $ g $ - free子集的$ v（h）$，如果$ v（h）$ $ v（h）$，则$ v（g）} \ rceil $ - 如果$ v（h）$ h $满足以下条件； （1）$ h $如果$ g $是常规的，（2）$ h $不是$ k_ {kΔ（g）+1} $如果$ g \ simeq k_ {Δ（g）+1} $ g \ s+g $ g $ g $ isomorphic comorphic，则不是同构的。实际上，我们通过证明$ g_1，\ ldots，g_k $的图形是最低度的$ d_1，\ ldots，d_k $，并且$Δ（h）= \ sum_ {i = 1}^{k} d_k $，然后是$ h $ h $ h $ h， 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 $不是同构至$ k_ {δ（h）+1} $，或者每个$ g_i $都是同构为$ k_ {2} $，而$ h $不是一个奇怪的周期。
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.
