{
  "id": "2405.17819",
  "version": "v1",
  "published": "2024-05-28T04:38:40.000Z",
  "updated": "2024-05-28T04:38:40.000Z",
  "title": "An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs",
  "authors": [
    "Arnab Char",
    "T. Karthick"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Given a graph $G$, the parameters $\\chi(G)$ and $\\omega(G)$ respectively denote the chromatic number and the clique number of $G$. A function $f : \\mathbb{N} \\rightarrow \\mathbb{N}$ such that $f(1) = 1$ and $f(x) \\geq x$, for all $x \\in \\mathbb{N}$ is called a $\\chi$-binding function for the given class of graphs $\\cal{G}$ if every $G \\in \\cal{G}$ satisfies $\\chi(G) \\leq f(\\omega(G))$, and the \\emph{smallest $\\chi$-binding function} $f^*$ for $\\cal{G}$ is defined as $f^*(x) := \\max\\{\\chi(G)\\mid G\\in {\\cal G} \\mbox{ and } \\omega(G)=x\\}$. In general, the problem of obtaining the smallest $\\chi$-binding function for the given class of graphs seems to be extremely hard, and only a few classes of graphs are studied in this direction. In this paper, we study the class of ($P_2+ P_3$, gem)-free graphs, and prove that the function $\\phi:\\mathbb{N}\\rightarrow \\mathbb{N}$ defined by $\\phi(1)=1$, $\\phi(2)=4$, $\\phi(3)=6$ and $\\phi(x)=\\left\\lceil\\frac{1}{4}(5x-1)\\right\\rceil$, for $x\\geq 4$ is the smallest $\\chi$-binding function for the class of ($P_2+ P_3$, gem)-free graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-05-28T04:38:40.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "optimal chromatic bound",
      "binding function",
      "chromatic number",
      "clique number",
      "parameters"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}