{
  "id": "2106.08871",
  "version": "v1",
  "published": "2021-06-16T15:45:01.000Z",
  "updated": "2021-06-16T15:45:01.000Z",
  "title": "Polynomial $χ$-binding functions for $t$-broom-free graphs",
  "authors": [
    "Xiaonan Liu",
    "Joshua Schroeder",
    "Zhiyu Wang",
    "Xingxing Yu"
  ],
  "comment": "14 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "For any positive integer $t$, a \\emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing an edge once. In this paper, we show that, for graphs $G$ without induced $t$-brooms, we have $\\chi(G) = o(\\omega(G)^{t+1})$, where $\\chi(G)$ and $\\omega(G)$ are the chromatic number and clique number of $G$, respectively. When $t=2$, this answers a question of Schiermeyer and Randerath. Moreover, for $t=2$, we strengthen the bound on $\\chi(G)$ to $7.5\\omega(G)^2$, confirming a conjecture of Sivaraman. For $t\\geq 3$ and \\{$t$-broom, $K_{t,t}$\\}-free graphs, we improve the bound to $o(\\omega^{t-1+\\frac{2}{t+1}})$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-16T15:45:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C17",
      "05C75"
    ],
    "keywords": [
      "broom-free graphs",
      "binding functions",
      "polynomial",
      "chromatic number",
      "clique number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}