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

DOI10.1002/JGT.21684zbMATH Open1269.05062arXiv1109.3092OpenAlexW2963439943MaRDI QIDQ5325947FDOQ5325947

Authors: Demetres Christofides, Katherine Edwards, Andrew D. King 

Publication date: 31 July 2013

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)