{
  "id": "2212.05239",
  "version": "v1",
  "published": "2022-12-10T07:58:46.000Z",
  "updated": "2022-12-10T07:58:46.000Z",
  "title": "The optimal $χ$-bound for $(P_7,C_4,C_5)$-free graphs",
  "authors": [
    "Shenwei Huang"
  ],
  "comment": "21 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we give an optimal $\\chi$-binding function for the class of $(P_7,C_4,C_5)$-free graphs. We show that every $(P_7,C_4,C_5)$-free graph $G$ has $\\chi(G)\\le \\lceil \\frac{11}{9}\\omega(G) \\rceil$. To prove the result, we use a decomposition theorem obtained in [K. Cameron and S. Huang and I. Penev and V. Sivaraman, The class of $({P}_7,{C}_4,{C}_5)$-free graphs: Decomposition, algorithms, and $\\chi$-boundedness, Journal of Graph Theory 93, 503--552, 2020] combined with careful inductive arguments and a nontrivial use of the K\\\"{o}nig theorem for bipartite matching.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-10T07:58:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "decomposition theorem",
      "graph theory",
      "binding function",
      "algorithms"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}