Reeds conjecture on some special classes of graphsReport as inadecuate

Reeds conjecture on some special classes of graphs - Download this document for free, or read online. Document in PDF available to download.

1 LIFO - Laboratoire d-Informatique Fondamentale d-Orléans

Abstract : Reed conjectured that for any graph $G$, $\chiG \leq \lceil \frac{\omegaG+\DeltaG+1}{2} ceil$, where $\chiG$, $\omegaG$, and $\DeltaG$ respectively denote the chromatic number, the clique number and the maximum degree of $G$. In this paper, we verify this conjecture for some special classes of graphs, in particular for subclasses of $P 5$-free graphs or $Chair$-free graphs.

Keywords : Vertex coloring Chromatic number Clique number Maximum degree

Author: Jean-Luc Fouquet - Jean-Marie Vanherpe -



Related documents