✦ LIBER ✦

Improved bounds for the chromatic number of a graph

✍ Scribed by S. Louis Hakimi; Edward Schmeichel

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 97 KB
Volume: 47
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20032

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

After giving a new proof of a well‐known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres‐Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge‐cut (V~1~, V~2~) in a graph G, together with colorings of 〈V~1~〉 and 〈V~2~〉, what is the least number of colors in a coloring of G which “respects” the colorings of 〈V~1~〉 and 〈V~2~〉 ? We give a constructive optimal solution of this problem, and use it to derive a new upper bound for the chromatic number of a graph. As easy corollaries, we obtain several interesting bounds which also appear to be new, as well as classical bounds of Dirac and Ore, and the above mentioned bounds of Matula and Szekeres‐Wilf. We conclude by considering two algorithms suggested by our results. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 217–225, 2004

📜 SIMILAR VOLUMES

Bounds for the harmonious chromatic numb

Bounds for the harmonious chromatic number of a graph

✍ I. Krasikov; Y. Roditty 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph given by Zhikang Lu and by C. McDiarmid and Luo Xinhua, independently (__Journal of Graph Theory__, 1991, pp. 345–347 and 629–636) and the lower bound given by D. G. Beane, N. L. Biggs, and B. J. Wilson (__Journal of Graph T

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 3 views

New bounds for the chromatic number of g

New bounds for the chromatic number of graphs

✍ Manouchehr Zaker 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract In this article 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 11. Next, we obtain an upper bound of the order of magnitude ${\cal O}({n}^{{1}-\epsilon})$ for the coloring number of a graph

An improved bound for the strong chromat

An improved bound for the strong chromatic number

✍ P. E. Haxell 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB 👁 1 views

## Abstract Let η > 0 be given. Then there exists __d__~0~ = __d__~0~(η) such that the following holds. Let __G__ be a finite graph with maximum degree at most __d__ ≥ __d__~0~ whose vertex set is partitioned into classes of size α __d__, where α≥ 11/4 + η. Then there exists a proper coloring of __

An upper bound for the harmonious chroma

An upper bound for the harmonious chromatic number of a graph

✍ Sin-Min Lee; John Mitchem 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o

A lower bound on the chromatic number of

A lower bound on the chromatic number of a graph

✍ B. R. Myers; R. Liu 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views