# zbMATH — the first resource for mathematics

On $$(\delta, \chi)$$-bounded families of graphs. (English) Zbl 1217.05091
Summary: A family $$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)$$ denote the minimum degree and chromatic number of $$G$$, respectively. Also for any set $${H_1, H_2, \dots , H_k}$$ of graphs by $$F orb(H_1, H_2, \dots , H_k)$$ we mean the class of graphs that contain no $$H_i$$ as an induced subgraph for any $$i = 1, \dots , 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$$, $$F orb(T, K\ell ,\ell )$$ is a $$(\delta , \chi )$$-bounded family. Then we obtain a necessary and sufficient condition for $$F orb(H_1, H_2, \dots , H_k)$$ to be a $$(\delta , \chi )$$-bounded family, where $${H_1, H_2, \dots , H_k}$$ is any given set of graphs. Next we study $$(\delta , \chi )$$-boundedness of $$F orb(C)$$ where $$C$$ is an infinite collection of graphs. We show that for any positive integer $$\ell$$, $$F orb(K\ell ,\ell , C6, C8, \dots)$$ is $$(\delta , \chi )$$-bounded. Finally we show a similar result when $$C$$ is a collection consisting of unicyclic graphs.
##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory
Full Text: