Reed's conjecture on some special classes of graphs

2012/05/03 by Fouquet, Jean-Luc, Vanherpe, Jean-Marie
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1205.0730

Abstract

Reed conjectured that for any graph G, χ(G) ≤ \lceil (ω(G)+Δ(G)+1)/(2)\rceil, where χ(G), ω(G), and Δ(G) 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₅-free graphs or Chair-free graphs.

Related

• A note on Reed's Conjecture about \ω, \Δ and \χ with\n respect to vertices of high degree
• Reed's Conjecture on hole expansions
• A note on Reed's conjecture
• An analogue of Reed's conjecture for digraphs
• Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications