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

DOI10.1002/jgt.21684zbMath1269.05062arXiv1109.3092OpenAlexW2963439943MaRDI QIDQ5325947

Andrew D. King, Katherine Edwards, Demetres Christofides

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

stable setgraph coloringmaximum cliquemaximal cliqueReeds conjecture

Mathematics Subject Classification ID

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

Related Items (8)

Two more characterizations of König-Egerváry graphs ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ A set and collection lemma ⋮ Partitioning of a graph into induced subgraphs not containing prescribed cliques ⋮ On bounding the difference of the maximum degree and the clique number ⋮ Unnamed Item ⋮ Finding independent transversals efficiently ⋮ A note on coloring vertex-transitive graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Hajos' graph-coloring conjecture: Variations and counterexamples
• A condition for matchability in hypergraphs
• Independent systems of representatives in weighted graphs
• 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

This page was built for publication: A Note on Hitting Maximum and Maximal Cliques With a Stable Set