Home » Subject » Graph Theory

Hitting every large maximal clique with a stable set (Solved)

Importance: Medium ✭✭
Author(s): King, Andrew D.
Rabern, L.
Subject: Graph Theory
Keywords: independent set
maximal clique
Recomm. for undergrads: yes
Posted by: Andrew King
on: March 31st, 2011
Solved by:
Conjecture   There is a universal constant $ \epsilon>0 $ such that every graph contains a stable set which intersects every maximal clique of size $ (1-\epsilon)(\Delta+1) $.

Conjecture   Every graph contains a stable set which intersects every maximal clique of size $ >\frac{2}{3}(\Delta+1) $.

Both forms of the conjecture are false, as shown by the following counterexample.

Take sufficiently large integers $ k $ and $ t $, and let $ X_1,\ldots, X_t $ be disjoint $ k $-cliques, such that their union is a clique of size $ kt $. Now add $ t $ disjoint copies of $ C_5 $, labelled $ Y_1,\ldots, Y_t $, with no edges between them and such that $ Y_i $ is complete to $ X_j $ if $ i\neq j $ and anticomplete otherwise.

This graph has $ (k+5)t $ vertices and maximum degree $ (k+5)t - 6 $. Every edge in $ Y_i $ is in a maximal clique of size $ k(t-1)+2 $. It is straightforward to show that for every $ \epsilon>0 $ we can choose $ k $ and $ t $ sufficiently large that this graph is a counterexample.

The original discussion of the conjecture follows.

King [K] proved that any graph $ G $ with $ \omega>\frac{2}{3}(\Delta+1) $ contains a stable set intersecting every maximum clique. This used the same approach as Rabern's earlier proof for graphs with $ \omega\geq \frac{3}{4}(\Delta+1) $, but exploited a more general existence condition for independent systems of representatives.

One of the key lemmas is Hajnal's clique collection lemma, which states that for any collection of maximum cliques in a graph, the sum of the intersection and the union is at least $ 2\omega $. Unfortunately the same result does not hold when restricted to large maximal cliques. Thus the case of maximal cliques would require a different approach.

This conjecture is motivated by a local strengthening of Reed's omega, Delta, chi conjecture.

Related problems

Reed's omega, delta, and chi conjecture

Bibliography

[K] Andrew D. King. Hitting all maximum cliques with a stable set using lopsided independent transversals, J. Graph Theory, n/a, doi: 10.1002/jgt.20532.

[R] Landon Rabern. On hitting all maximum cliques with an independent set, J. Graph Theory, 66 (2010), 32--37, doi: 10.1002/jgt.20487.


* indicates original appearance(s) of problem.
add new comment