Towards Esperet's Conjecture: Polynomial $\ddot{I}‡$-Bounds for Structured Graph Classes

Abstract

In this paper, we establish that the class of $\{P_6,(2,2)\text{-broom}\}$-free graphs contains a subclass ${\mathcal{L}}_i$, defined by certain cutset conditions, whose chromatic number admits a linear $\ddot{I}‡$-bound. Building on recent results showing that broom-free graphs excluding $K_d(t)$ as a subgraph admit a polynomial bound in~$t$ on their chromatic number (A broom is obtained from a path with one end $v$ by adding leaves adjacent to $v$), we extend this result to the hereditary class $\mathcal{H}$ of $C_4$-free and \emph{$p$-flag}-free graphs (where a \emph{$p$-flag} is a triangle with an attached $p$-path). We show that if $G\in \mathcal{H}$ is $B^{+}(p+2,t-1)$-free (for $p\ge 2$ and $t\ge 3$, that is, if it excludes a generalized broom with an additional leaf), and does not contain $K_d(t)$ as a subgraph, then $\ddot{I}‡(G)$ is polynomially bounded in $t$. Furthermore, for the subclass of $\mathcal{H}$ excluding $K_3(t)$ as a subgraph, we prove that $\ddot{I}‡(G)$ is linearly $\ddot{I}‡$-bounded in $\ddot{I}‰(G)$.

12 pages