On lower bounds for the chromatic number in terms of vertex degree

被引:3
作者
Zaker, Manouchehr [1 ]
机构
[1] Inst Adv Studies Basic Sci, Dept Math, Zanjan 4513766731, Iran
关键词
Graph coloring; Chromatic number; Vertex degree; Coloring number;
D O I
10.1016/j.disc.2011.03.025
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 K-1,K-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 K-2,K-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 delta-bounded families of graphs and then we obtain a necessary and sufficient condition for a family of graphs to be a delta-bounded family in terms of its induced bipartite Turn 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, beta-perfect graphs, J. Combin. Theory Ser. B 67 (1996)1-11]. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:1365 / 1370
页数:6
相关论文
共 10 条
[1]  
[Anonymous], 2008, Graph Theory
[2]  
Diestel R., 2000, Graph Theory
[3]   ON INDEPENDENT GENERALIZED DEGREES AND INDEPENDENCE NUMBERS IN K(1,M)-FREE GRAPHS [J].
FAUDREE, RJ ;
GOULD, RJ ;
JACOBSON, MS ;
LESNIAK, LM ;
LINDQUESTER, TE .
DISCRETE MATHEMATICS, 1992, 103 (01) :17-24
[4]   INDUCED SUBTREES IN GRAPHS OF LARGE CHROMATIC NUMBER [J].
GYARFAS, A ;
SZEMEREDI, E ;
TUZA, Z .
DISCRETE MATHEMATICS, 1980, 30 (03) :235-244
[5]  
Jensen T., 1995, Graph Coloring Problems, P115
[6]  
LI H, 1990, ARS COMBIN A, V29, P109
[7]   beta-Perfect graphs [J].
Markossian, SE ;
Gasparian, GS ;
Reed, BA .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 67 (01) :1-11
[8]  
SIMONOVITS M, 1983, SELECTED TOPICS GRAP, V2, P161
[9]  
Thomassen C., 1988, SELECTED TOPICS GRAP, P97
[10]   New bounds for the chromatic number of graphs [J].
Zaker, Manouchehr .
JOURNAL OF GRAPH THEORY, 2008, 58 (02) :110-122