×

New bounds for the chromatic number of graphs. (English) Zbl 1149.05018

Summary: We first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in [L. Stacho, J. Graph Theory 36, No.2, 117–120 (2001; Zbl 0971.05041)]. Next, we obtain an upper bound of the order of magnitude \(\mathcal O (n^{1-\varepsilon})\) for the coloring number of a graph with small \(K_{2,t}\) (as subgraph), where \(n\) is the order of the graph. Finally, we give some bounds for chromatic number in terms of girth and book size. These bounds improve the best known bound, in terms of order and girth, for the chromatic number of a graph when its girth is an even integer.

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0971.05041
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, J Combin Theory A 29 pp 354– (1980)
[2] Alon, Combinatorica 12 pp 125– (1992)
[3] Bollobás, Eur J Combin 26 pp 259– (2005)
[4] Brooks, Proc Camb Philos Soc 37 pp 194– (1941)
[5] Chung, J Graph Theory 25 pp 3– (1997)
[6] Erdos, Discrete Math 53 pp 281– (1985)
[7] and , Graph Coloring Problems, John Wiley & Sons, New York, 1995. · Zbl 0855.05054
[8] Kim, Rand Struct Algorithm 7 pp 173– (1995)
[9] Combinatorial Problems and Exercises, North-Holland Publishing Co., Amsterdam, New York, 1979. · Zbl 0439.05001
[10] Spencer, Discrete Math 20 pp 69– (1977)
[11] Stacho, J Graph Theory 36 pp 117– (2001)
[12] Zaker, Australas J Combin 31 pp 325– (2005)
[13] Zaker, Discrete Math 306 pp 3166– (2006)
[14] Zaker, Discrete Appl Math 155 pp 2567– (2007)
[15] The chromatic number of graphs and book sizes, manuscript 2007.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.