{
  "id": "2501.04923",
  "version": "v1",
  "published": "2025-01-09T02:23:29.000Z",
  "updated": "2025-01-09T02:23:29.000Z",
  "title": "Critical $(P_5,W_4)$-Free Graphs",
  "authors": [
    "Wen Xia",
    "Jorik Jooken",
    "Jan Goedgebeur",
    "Iain Beaton",
    "Ben Cameron",
    "Shenwei Huang"
  ],
  "comment": "arXiv admin note: text overlap with arXiv:2308.03414, arXiv:2403.05611",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph $G$ is $k$-vertex-critical if $\\chi(G) = k$ but $\\chi(G-v)<k$ for all $v \\in V(G)$. A graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ nor $H_2$. A $W_4$ is the graph consisting of a $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$. We show that there are finitely many $k$-vertex-critical $(P_5,W_4)$-free graphs for all $k \\ge 1$ and we characterize all $5$-vertex-critical $(P_5,W_4)$-free graphs. Our results imply the existence of a polynomial-time certifying algorithm to decide the $k$-colorability of $(P_5,W_4)$-free graphs for each $k \\ge 1$ where the certificate is either a $k$-coloring or a $(k+1)$-vertex-critical induced subgraph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-01-09T02:23:29.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graphs",
      "additional vertex adjacent",
      "polynomial-time certifying algorithm",
      "induced subgraph isomorphic",
      "vertex-critical"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}