pith. sign in

arxiv: 0907.3705 · v3 · submitted 2009-07-21 · 🧮 math.CO

On hitting all maximum cliques with an independent set

classification 🧮 math.CO
keywords omegadeltalceilrceileveryfracindependentprove
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.