On hitting all maximum cliques with an independent set

DOI10.1002/jgt.20487zbMath1222.05201arXiv0907.3705OpenAlexW2123831997MaRDI QIDQ3067059

Landon Rabern

Publication date: 20 January 2011

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

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

zbMATH Keywords

line graphcliquecoloringReed's 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 (17)

Brooks' Theorem and Beyond ⋮ A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω ⋮ A Note on Hitting Maximum and Maximal Cliques With a Stable Set ⋮ Two more characterizations of König-Egerváry graphs ⋮ On the independent domination number of regular graphs ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ The Success Probability in Levine’s Hat Problem, and Independent Sets in Graphs ⋮ A set and collection lemma ⋮ Special issue in honour of Landon Rabern ⋮ Partitioning of a graph into induced subgraphs not containing prescribed cliques ⋮ Hitting all maximum stable sets in \(P_5\)-free graphs ⋮ Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker ⋮ A structural approach for independent domination of regular graphs ⋮ Hitting all maximum cliques with a stable set using lopsided independent transversals ⋮ A different short proof of Brooks' theorem ⋮ Finding independent transversals efficiently ⋮ A note on coloring vertex-transitive graphs

Cites Work

• Unnamed Item
• Improving a family of approximation algorithms to edge color multigraphs
• An upper bound for the chromatic number of line graphs
• A Note on Vertex List Colouring
• A Theorem on k-Saturated Graphs

This page was built for publication: On hitting all maximum cliques with an independent set