Premium
On hitting all maximum cliques with an independent set
Author(s) -
Rabern Landon
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20487
Subject(s) - mathematics , combinatorics , counterexample , conjecture , cubic graph , graph , discrete mathematics , line graph , voltage graph
We prove that every graph G for which has an independent set I such that ω( G − I )<ω( G ). It follows that a minimum counterexample G to Reed's conjecture satisfies and hence also . This also applies to restrictions of Reed's conjecture to hereditary graph classes, and in particular generalizes and simplifies King, Reed and Vetta's proof of Reed's conjecture for line graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 32–37, 2010