{
  "id": "2007.00057",
  "version": "v1",
  "published": "2020-06-30T18:40:09.000Z",
  "updated": "2020-06-30T18:40:09.000Z",
  "title": "Dichotomizing $k$-vertex-critical $H$-free graphs for $H$ of order four",
  "authors": [
    "Ben Cameron",
    "Chính T. Hoàng",
    "Joe Sawada"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "For $k \\geq 3$, we prove (i) there is a finite number of $k$-vertex-critical $(P_2+\\ell P_1)$-free graphs and (ii) $k$-vertex-critical $(P_3+P_1)$-free graphs have at most $2k-1$ vertices. Together with previous research, these results imply the following characterization where $H$ is a graph of order four: There is a finite number of $k$-vertex-critical $H$-free graphs for fixed $k \\geq 5$ if and only if $H$ is one of $\\overline{K_4}, P_4, P_2 + 2P_1$, or $P_3 + P_1$. Our results imply the existence of new polynomial-time certifying algorithms for deciding the $k$-colorability of $(P_2+\\ell P_1)$-free graphs for fixed $k$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-30T18:40:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graphs",
      "vertex-critical",
      "finite number",
      "dichotomizing"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}