{
  "id": "1302.3811",
  "version": "v1",
  "published": "2013-02-15T17:16:29.000Z",
  "updated": "2013-02-15T17:16:29.000Z",
  "title": "Indicated coloring of matroids",
  "authors": [
    "Michał Lasoń"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A coloring of a matroid is proper if elements of the same color form an independent set. For a loopless matroid M, its chromatic number \\chi(M) is the minimum number of colors that suffices to color properly the ground set E of M. In this note we study a game-theoretic variant of this parameter proposed by Grytczuk. Suppose that in each round of the game Alice indicates an uncolored yet element e of E, then Bob colors it using a color from a fixed set of colors C. The rule Bob has to obey is that it is a proper coloring. The game ends if the whole matroid has been colored or if Bob can not color e using any color of C. Alice wins in the first case, while Bob in the second. The minimum size of the set of colors C for which Alice has a winning strategy is called the indicated chromatic number of M, denoted by \\chi_i(M). We prove that \\chi_i(M)=\\chi(M).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-02-15T17:16:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05B35"
    ],
    "keywords": [
      "chromatic number",
      "independent set",
      "minimum number",
      "ground set",
      "first case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.3811L"
    }
  }
}