Header menu link for other important links
X
Bounding χ in terms of ω and Δ for some classes of graphs
, T. Karthick, C.R. Subramanian
Published in
2011
Volume: 311
   
Issue: 12
Pages: 911 - 920
Abstract
Reed [B. Reed, ω,Δ and χ, Journal of Graph Theory, 27 (1998) 177-212] conjectured that for any graph G, χ(G)≤Δ(G) +ω(G)+12⌉, 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 which are defined by families of forbidden induced subgraphs. © 2011 Elsevier B.V. All rights reserved.
About the journal
JournalDiscrete Mathematics
ISSN0012365X