Improved bounds for the chromatic number of a graph

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 (V1, V2) in a graph G, toget...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2004-11, Vol.47 (3), p.217-225
Main Authors: Hakimi, S. Louis, Schmeichel, Edward
Format: Article
Language:English
Subjects:
chromatic number
critical graphs
graph coloring algorithms
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (V1, V2) in a graph G, together with colorings of 〈V1〉 and 〈V2〉, what is the least number of colors in a coloring of G which “respects” the colorings of 〈V1〉 and 〈V2〉 ? 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
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.20032