On hitting all maximum cliques with an independent set

We prove that every graph $G$ for which $ω(G) \geq 3/4(Δ(G) + 1)$, has an independent set $I$ such that $ω(G - I) < ω(G)$. It follows that a minimum counterexample $G$ to Reed's conjecture satisfies $ω(G) < 3/4(Δ(G) + 1)$ and hence also $χ(G) > \lceil 7/6ω(G) \rceil$. We also prove that if for every induced subgraph $H$ of $G$ we have $χ(H) \leq \max{\lceil 7/6ω(H) \rceil, \lceil \frac{ω(H) + Δ(H) + 1}{2}\rceil}$, then we also have $χ(G) \leq \lceil \frac{ω(G) + Δ(G) + 1}{2}\rceil$. This gives a generic proof of the upper bound for line graphs of multigraphs proved by King et al.

No reviews yet.

No comments yet.