{
  "id": "2207.08168",
  "version": "v1",
  "published": "2022-07-17T13:12:15.000Z",
  "updated": "2022-07-17T13:12:15.000Z",
  "title": "$χ$-binding function for a superclass of $2K_2$-free graphs",
  "authors": [
    "Athmakoori Prashant",
    "S. Francis Raj"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The class of $2K_2$-free graphs has been well studied in various contexts in the past. In this paper, we study the chromatic number of $\\{butterfly, hammer\\}$-free graphs, a superclass of $2K_2$-free graphs and show that a connected $\\{butterfly, hammer\\}$-free graph $G$ with $\\omega(G)\\neq 2$ admits $\\binom{\\omega+1}{2}$ as a $\\chi$-binding function which is also the best available $\\chi$-binding function for its subclass of $2K_2$-free graphs. In addition, we show that if $H\\in\\{C_4+K_p, P_4+K_p\\}$, then any $\\{butterfly, hammer, H\\}$-free graph $G$ with no components of clique size two admits a linear $\\chi$-binding function. Furthermore, we also establish that any connected $\\{butterfly, hammer, H\\}$-free graph $G$ where $H\\in \\{(K_1\\cup K_2)+K_p, 2K_1+K_p\\}$, is perfect for $\\omega(G)\\geq 2p$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-07-17T13:12:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "binding function",
      "superclass",
      "chromatic number",
      "components"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}