{
  "id": "2311.05231",
  "version": "v1",
  "published": "2023-11-09T09:18:56.000Z",
  "updated": "2023-11-09T09:18:56.000Z",
  "title": "An optimal chromatic bound for the class of $\\{P_3\\cup 2K_1,\\overline{P_3\\cup 2K_1}\\}$-free graphs",
  "authors": [
    "Athmakoori Prashant",
    "S. Francis Raj"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1987, A. Gy\\'arf\\'as in his paper ``Problems from the world surrounding perfect graphs'' posed the problem of determining the smallest $\\chi$-binding function for $\\mathcal{G}(F,\\overline{F})$, when $\\mathcal{G}(F)$ is $\\chi$-bounded. So far the problem has been attempted for only forest $F$ with four or five vertices. In this paper, we address the case when $F=P_3\\cup 2K_1$ and show that if $G$ is a $\\{P_3\\cup 2K_1,\\overline{P_3\\cup 2K_1}\\}$-free graph with $\\omega(G)\\neq 3$, then it admits $\\omega(G)+1$ as a $\\chi$-binding function. Moreover, we also construct examples to show that this bound is tight for all values of $\\omega\\neq 3$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-11-09T09:18:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "optimal chromatic bound",
      "free graph",
      "binding function",
      "world surrounding perfect graphs",
      "construct examples"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}