{
  "id": "1403.8027",
  "version": "v2",
  "published": "2014-03-31T14:47:40.000Z",
  "updated": "2014-11-27T02:55:16.000Z",
  "title": "On color-critical ($P_{5},\\overline{P}_5$)-free graphs",
  "authors": [
    "Harjinder S. Dhaliwal",
    "Angèle M. Hamel",
    "Chính T. Hoàng",
    "Frédéric Maffray",
    "Tyler J. D. McConnell",
    "Stefan A. Panait"
  ],
  "comment": "13 pages, minor revisions made",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph is $k$-critical if it is $k$-chromatic but each of its proper induced subgraphs is ($k-1$)-colorable. It is known that the number of $4$-critical $P_5$-free graphs is finite, but there is an infinite number of $k$-critical $P_5$-free graphs for each $k \\geq 5$. We show that the number of $k$-critical $(P_5, \\overline{P}_5)$-free graphs is finite for every fixed $k$. Our result implies the existence of a certifying algorithm for $k$-coloring $(P_5, \\overline{P}_5)$-free graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-03-31T14:47:40.000Z",
      "comment": "11 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-11-27T02:55:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graphs",
      "result implies",
      "infinite number",
      "proper induced subgraphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1403.8027D"
    }
  }
}