A note on hitting maximum and maximal cliques with a stable set

DOI10.1002/JGT.21684MaRDI QIDQ5325947zbMATH OpenOpenAlexFDO

Authors Demetres Christofides, Katherine Edwards, Andrew D. King

Publication date 31 July 2013

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3092

zbMATH Keywords

maximum cliquegraph coloringstable setmaximal cliqueReeds conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: It was recently proved that any graph satisfying $omega>frac23(Delta+1)$ contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satisfying $omegageqfrac23(Delta+1)$ unless the graph is the strong product of $K_{omega/2}$ and an odd hole. We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.

Recommendations

• Hitting all maximum cliques with a stable set using lopsided independent transversals
• On hitting all maximum cliques with an independent set
• Covering all cliques of a graph
• Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
• Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs

Cites work

• scientific article; zbMATH DE number 3719178 (Why is no real title available?)
• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• A Theorem on k-Saturated Graphs
• A condition for matchability in hypergraphs
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• Independent systems of representatives in weighted graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• On hitting all maximum cliques with an independent set

Cited in

(13)

• A note on coloring vertex-transitive graphs
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• A set and collection lemma
• Two more characterizations of König-Egerváry graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Partitioning of a graph into induced subgraphs not containing prescribed cliques
• scientific article; zbMATH DE number 7641240 (Why is no real title available?)
• Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs
• The stable set problem: clique and nodal inequalities revisited
• Graphs with \(\chi=\Delta\) have big cliques
• On bounding the difference of the maximum degree and the clique number
• Finding independent transversals efficiently
• Towards Erdős-Hajnal for graphs with no 5-hole

This page was built for publication: A note on hitting maximum and maximal cliques with a stable set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5325947)