On \((\delta, \chi)\)-bounded families of graphs
type: Item
instance of: scholarly article
title: On \((\delta, \chi)\)-bounded families of graphs
zbMATH Open document ID: 1217.05091
author: András Gyárfás
author: Manouchehr Zaker
published in: The Electronic Journal of Combinatorics
publication date: 2011-06-01T00:00:00Z
full work available at URL: https://eudml.org/doc/230407
full work available at URL: v18i1p108.html
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5903038
MaRDI profile type: Publication
Recommended article: $(\delta, \chi_{_{\sf FF}})$-bounded families of graphs
Recommended article: χ‐bounded families of oriented graphs
Recommended article: Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
Recommended article: Bounding χ in terms of ω and Δ for quasi-line graphs
Recommended article: Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
Recommended article: Q6054225
Recommended article: Bounds for the b-chromatic number of some families of graphs
Recommended article: Q4718965
Recommended article: On Delta Graphs and Delta Conjecture
Recommended article: A note on \(\Delta\)-critical graphs
description: scientific article; zbMATH DE number 5903038