|
|||||
|
|
A Note on Hitting Maximum and Maximal Cliques With a Stable Set |
|
| Authors: | Demetres Christofides Katherine Edwards Andrew D King |
| Institution: | 1. SCHOOL OF MATHEMATICAL SCIENCES, QUEEN MARY UNIVERSITY OF LONDON, , LONDON;2. DEPARTMENT OF COMPUTER SCIENCE, PRINCETON UNIVERSITY, , PRINCETON, NJ;3. DEPARTMENTS OF MATHEMATICS AND COMPUTING SCIENCE, SIMON FRASER UNIVERSITY, , BURNABY, BC |
| Abstract: | It was recently proved that any graph satisfying  contains a stable set hitting every maximum clique. In this note, we prove that the same is true for graphs satisfying  unless the graph is the strong product of an odd hole and  .We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique. |
| Keywords: | maximum clique stable set maximal clique Reed‗ s conjecture graph coloring |