{
  "id": "1310.7964",
  "version": "v1",
  "published": "2013-10-29T20:56:02.000Z",
  "updated": "2013-10-29T20:56:02.000Z",
  "title": "Approximability of the upper chromatic number of hypergraphs",
  "authors": [
    "Csilla Bujtás",
    "Zsolt Tuza"
  ],
  "comment": "18 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A C-coloring of a hypergraph ${\\cal H}=(X,{\\cal E})$ is a vertex coloring $\\varphi: X\\to {\\mathbb{N}}$ such that each edge $E\\in{\\cal E}$ has at least two vertices with a common color. The related parameter $\\overline{\\chi}({\\cal H})$, called the upper chromatic number of ${\\cal H}$, is the maximum number of colors can be used in a C-coloring of ${\\cal H}$. A hypertree is a hypergraph which has a host tree $T$ such that each edge $E\\in {\\cal E}$ induces a connected subgraph in $T$. Notations $n$ and $m$ stand for the number of vertices and edges, respectively, in a generic input hypergraph. We establish guaranteed polynomial-time approximation ratios for the difference $n-\\overline{\\chi}({\\cal H})$, which is $2+2 \\ln (2m)$ on hypergraphs in general, and $1+ \\ln m$ on hypertrees. The latter ratio is essentially tight as we show that $n-\\overline{\\chi}({\\cal H})$ cannot be approximated within $(1-\\epsilon) \\ln m$ on hypertrees (unless ${\\sf NP} \\subseteq {\\sf DTIME} (n^{{\\cal O}(log\\;log\\; n)})$). Furthermore, $\\overline{\\chi}({\\cal H})$ does not have ${\\cal O}(n^{1-\\epsilon})$-approximation and cannot be approximated within additive error $o(n)$ on the class of hypertrees (unless ${\\sf P}={\\sf NP}$).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-10-29T20:56:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C65",
      "05B40",
      "68Q17"
    ],
    "keywords": [
      "upper chromatic number",
      "approximability",
      "generic input hypergraph",
      "establish guaranteed polynomial-time approximation ratios",
      "common color"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1310.7964B"
    }
  }
}