{
  "id": "1802.09503",
  "version": "v1",
  "published": "2018-02-26T18:36:09.000Z",
  "updated": "2018-02-26T18:36:09.000Z",
  "title": "Online Coloring of Short Intervals",
  "authors": [
    "Grzegorz Gutowski",
    "Konstanty Junosza-Szaniawski",
    "Patryk Mikos",
    "Adam Polak",
    "Joanna Sokół"
  ],
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.DS"
  ],
  "abstract": "We study the online graph coloring problem restricted to the intersection graphs of intervals with lengths in $[1,\\sigma]$. For $\\sigma=1$ it is the class of unit interval graphs, and for $\\sigma=\\infty$ the class of all interval graphs. Our focus is on intermediary classes. We present a $(1+\\sigma)$-competitive algorithm, which beats the state of the art for $1 < \\sigma < 2$. For $\\sigma = 1$ our algorithm matches the performance of FirstFit, which is $2$-competitive for unit interval graphs. For $\\sigma=2$ it matches the Kierstead-Trotter algorithm, which is $3$-competitive for all interval graphs. On the lower bound side, we prove that no algorithm is better than $5/3$-competitive for any $\\sigma>1$, nor better than $7/4$-competitive for any $\\sigma>2$, nor better than $5/2$-competitive for arbitrarily large values of $\\sigma$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-02-26T18:36:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "short intervals",
      "online coloring",
      "unit interval graphs",
      "competitive",
      "lower bound side"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}