# Reeds conjecture on some special classes of graphs

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 -

Source: https://hal.archives-ouvertes.fr/