On $(\delta, \chi)$-Bounded Families of Graphs
András Gyárfás, Manouchehr Zaker · The Electronic Journal of Combinatorics · 2011
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2011
Abstract
A family ${\mathcal{F}}$ of graphs is said to be $(\delta,\chi)$-bounded if there exists a function $f(x)$ satisfying $f(x)\rightarrow \infty$ as $x\rightarrow \infty$, such that for any graph $G$ from the family, one has $f(\delta(G))\leq \chi(G)$, where $\delta(G)$ and $\chi(G)$ denotes the minimum degree and chromatic number of $G$, respectively. Also for any set $\{H_1, H_2, \ldots, H_k\}$ of graphs by $Forb(H_1, H_2, \ldots, H_k)$ we mean the class of graphs that contain no $H_i$ as an induced subgraph for any $i=1, \ldots, k$.
In this paper we first answer affirmatively the question raised by the second author by showing that for any tree $T$ and positive integer $\ell$, $Forb(T, K_{\ell, \ell})$ is a $(\delta, \chi)$-bounded family. Then we obtain a necessary and sufficient condition for $Forb(H_1, H_2, \ldots, H_k)$ to be a $(\delta, \chi)$-bounded family, where $\{H_1, H_2, \ldots, H_k\}$ is any given set of graphs. Next we study $(\delta, \chi)$-boundedness of $Forb({\mathcal{C}})$ where ${\mathcal{C}}$ is an infinite collection of graphs. We show that for any positive integer $\ell$, $Forb(K_{\ell,\ell}, C_6, C_8, \ldots)$ is $(\delta, \chi)$-bounded.
Finally we show a similar result when ${\mathcal{C}}$ is a collection consisting of unicyclic graphs.
Open the resolved locator · 10.37236/595
Metadata licence: OpenAlex metadata (CC0)