On (, )-bounded families of graphs
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.
- \((\delta, \chi_{\mathsf{FF}})\)-bounded families of graphs
- χ‐bounded families of oriented graphs
- Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
- scientific article; zbMATH DE number 7742925
- Bounds for the b-chromatic number of some families of graphs
- scientific article; zbMATH DE number 1383105
- On delta-graphs and delta conjecture
- A note on \(\Delta\)-critical graphs
- On lower bounds for the chromatic number in terms of vertex degree
- \((\delta, \chi_{\mathsf{FF}})\)-bounded families of graphs
- Radius two trees specify χ‐bounded classes
- χ‐bounded families of oriented graphs
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- A Local Strengthening of Reed's \omega, \Delta, \chi Conjecture for Quasi-line Graphs
- Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
This page was built for publication: On \((\delta, \chi)\)-bounded families of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540113)
