{
  "id": "1404.7259",
  "version": "v2",
  "published": "2014-04-29T07:10:15.000Z",
  "updated": "2015-10-09T11:19:51.000Z",
  "title": "Lower bounds for on-line graph colorings",
  "authors": [
    "Grzegorz Gutowski",
    "Jakub Kozik",
    "Piotr Micek",
    "Xuding Zhu"
  ],
  "doi": "10.1007/978-3-319-13075-0_40",
  "categories": [
    "math.CO",
    "cs.DS"
  ],
  "abstract": "We propose two strategies for Presenter in on-line graph coloring games. The first one constructs bipartite graphs and forces any on-line coloring algorithm to use $2\\log_2 n - 10$ colors, where $n$ is the number of vertices in the constructed graph. This is best possible up to an additive constant. The second strategy constructs graphs that contain neither $C_3$ nor $C_5$ as a subgraph and forces $\\Omega(\\frac{n}{\\log n}^\\frac{1}{3})$ colors. The best known on-line coloring algorithm for these graphs uses $O(n^{\\frac{1}{2}})$ colors.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-29T07:10:15.000Z",
      "abstract": "We propose three strategies for Presenter in on-line graph coloring games. The first one constructs bipartite graphs and forces any on-line coloring algorithm to use $2\\log_2 n - 10$ colors, where $n$ is the number of vertices in the constructed graph. This is best possible up to an additive constant. The second strategy constructs triangle-free graphs and forces $\\Omega(n^\\frac{1}{2})$ colors. The third one constructs graphs that contain neither $C_3$ nor $C_5$ as a subgraph and forces $\\Omega(\\frac{n}{\\log n}^\\frac{1}{3})$ colors. The existence of an on-line algorithm using $o(n)$ colors on triangle-free graphs remains a tantalizing open problem.",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-10-09T11:19:51.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lower bounds",
      "second strategy constructs triangle-free graphs",
      "constructs bipartite graphs",
      "on-line graph coloring games"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Springer"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.7259G"
    }
  }
}