Reeds conjecture on some special classes of graphsReportar como inadecuado

Reeds conjecture on some special classes of graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: Jean-Luc Fouquet - Jean-Marie Vanherpe -



Documentos relacionados