On \((\delta, \chi)\)-bounded families of graphs

András Gyárfás ; Manouchehr Zaker

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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.

Détail

DOI : 10.37236/595

Classification : 05C15, 05C35