On lower bounds for the chromatic number in terms of vertex degree |
| |
Authors: | Manouchehr Zaker |
| |
Institution: | aDepartment of Mathematics, Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran |
| |
Abstract: | In this paper we discuss the existence of lower bounds for the chromatic number of graphs in terms of the average degree or the coloring number of graphs. We obtain a lower bound for the chromatic number of K1,t-free graphs in terms of the maximum degree and show that the bound is tight. For any tree T, we obtain a lower bound for the chromatic number of any K2,t-free and T-free graph in terms of its average degree. This answers affirmatively a modified version of Problem 4.3 in T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995]. More generally, we discuss δ-bounded families of graphs and then we obtain a necessary and sufficient condition for a family of graphs to be a δ-bounded family in terms of its induced bipartite Turán number. Our last bound is in terms of forbidden induced even cycles in graphs; it extends a result in S.E. Markossian, G.S. Gasparian, B.A. Reed, β-perfect graphs, J. Combin. Theory Ser. B 67 (1996) 1–11]. |
| |
Keywords: | Graph coloring Chromatic number Vertex degree Coloring number |
本文献已被 ScienceDirect 等数据库收录! |
|