A Note on the Chromatic Number in Dense Graphs

Randerath, Bert and Triesch, Eberhard (2009) A Note on the Chromatic Number in Dense Graphs.
Technical Report , 8 p.


Almost twenty years ago Reed conjectured that the arithmetic mean of a trivial lower bound, the clique number of a graph, and a trivial upper bound, the maximum degree of a graph plus one, establishes a new upper bound for the chromatic number of a graph. The conjecture is satisfied for a number of special graph classes, e.g. the conjecture has recently been proven by Rabern and by Kohl and Schiermeyer for the family of graphs with independence number two. For this family of dense graphs we present an alternative proof of Reed's Conjecture and generalize this result slightly.

Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
Content information:
Deposit Information:
ZAIK Number: zaik2009-588
Depositing User: Bert Randerath
Date Deposited: 30 Apr 2009 00:00
Last Modified: 12 Jan 2012 09:36
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/588