Premium
Improved bounds for the chromatic number of a graph
Author(s) -
Hakimi S. Louis,
Schmeichel Edward
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20032
Subject(s) - mathematics , combinatorics , constructive , upper and lower bounds , edge coloring , critical graph , graph coloring , chromatic scale , graph , brooks' theorem , constructive proof , list coloring , discrete mathematics , dirac (video compression format) , graph theory , graph power , line graph , computer science , mathematical analysis , physics , operating system , process (computing) , nuclear physics , neutrino
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