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.
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: EMIS EuDML