{
  "id": "1612.04702",
  "version": "v1",
  "published": "2016-12-14T16:06:41.000Z",
  "updated": "2016-12-14T16:06:41.000Z",
  "title": "Online Sum-Paintability: Slow-Coloring of Trees",
  "authors": [
    "Gregory J. Puleo",
    "Douglas B. West"
  ],
  "comment": "12 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "The slow-coloring game is played by Lister and Painter on a graph $G$. On each round, Lister marks a nonempty subset $M$ of the remaining vertices, scoring $|M|$ points. Painter then gives a color to a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. Painter's goal is to minimize the total score; Lister seeks to maximize it. The score that each player can guarantee doing no worse than is the sum-color cost of $G$, written $\\mathring{\\rm s}(G)$. We develop a linear-time algorithm to compute $\\mathring{\\rm s}(G)$ when $G$ is a tree, enabling us to characterize the $n$-vertex trees with the largest and smallest values.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-12-14T16:06:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C57"
    ],
    "keywords": [
      "online sum-paintability",
      "game ends",
      "smallest values",
      "total score",
      "lister seeks"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}