On hitting all maximum cliques with an independent set

Details On hitting all maximum cliques with an independent set On hitting all maximum cliques with an independent set

2009-07-21

arxiv.org/abs/0907.3705v3

Mathematics

Combinatorics

Added simple proof of Kostochka's lemma.

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

On hitting all maximum cliques with an independent set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On hitting all maximum cliques with an independent set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On hitting all maximum cliques with an independent set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-176560