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

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.