𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Note on Hitting Maximum and Maximal Cliques With a Stable Set

✍ Scribed by Demetres Christofides; Katherine Edwards; Andrew D. King

Book ID
112121145
Publisher
John Wiley and Sons
Year
2012
Tongue
English
Weight
506 KB
Volume
73
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Hitting all maximum cliques with a stabl
Hitting all maximum cliques with a stable set using lopsided independent transversals
✍ Andrew D. King πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 82 KB

Rabern recently proved that any graph with β‰₯ 3 4 ( +1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with > 2 3 ( +1). This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding a

A note on cliques and independent sets
A note on cliques and independent sets
✍ Entringer, Roger C.; Goddard, Wayne; Henning, Michael A. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 58 KB πŸ‘ 2 views

For integers m, n β‰₯ 2, let f (m, n) be the minimum order of a graph where every vertex belongs to both a clique of cardinality m and an independent set of cardinality n. We show that f (m, n) = ( √ m -1 + √ n -1) 2 .

A note on stable sets, groups, and theor
A note on stable sets, groups, and theories with NIP
✍ Alf Onshuus; Ya'acov Peterzil πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 152 KB πŸ‘ 1 views

## Abstract Let __M__ be an arbitrary structure. Then we say that an __M__ ‐formula __Ο†__ (__x__) __defines a stable set in__ __M__ if every formula __Ο†__ (__x__) ∧ __Ξ±__ (__x__, __y__) is stable. We prove: If __G__ is an __M__ ‐definable group and every definable stable subset of __G__ has __U__ ‐