{
  "id": "2002.04702",
  "version": "v1",
  "published": "2020-02-11T21:45:01.000Z",
  "updated": "2020-02-11T21:45:01.000Z",
  "title": "A Catlin-type Theorem for Graph Partitioning Avoiding Prescribed Subgraphs",
  "authors": [
    "Yaser Rowshan",
    "Ali Taherkhani"
  ],
  "comment": "8 pages",
  "categories": [
    "math.CO"
  ],
  "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,\\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{\\Delta(H)\\over \\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,\\ldots,G_k$ are connected graphs with minimum degrees $d_1,\\ldots,d_k$, respectively, and $\\Delta(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_{\\Delta(H)+1}$, or each $G_i$ is isomorphic to $K_{2}$ and $H$ is not an odd cycle.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-02-11T21:45:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "graph partitioning avoiding prescribed subgraphs",
      "isomorphic",
      "catlin-type theorem",
      "odd cycle",
      "color classes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}