Hitting all maximum cliques with a stable set using lopsided independent transversals

DOI10.1002/jgt.20532zbMath1231.05205arXiv0911.1741OpenAlexW3102475097MaRDI QIDQ5199419

Andrew D. King

Publication date: 16 August 2011

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

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

zbMATH Keywords

stable setgraph coloringmaximum cliqueindependent transversalindependent system of representatives

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (23)

Colouring graphs with sparse neighbourhoods: bounds and applications ⋮ 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 ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ When removing an independent set is optimal for reducing the chromatic number ⋮ A note on \(\Delta\)-critical graphs ⋮ A set and collection lemma ⋮ Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings ⋮ On the list coloring version of Reed's conjecture ⋮ Large cliques in graphs with high chromatic number ⋮ The clique problem with multiple-choice constraints under a cycle-free dependency graph ⋮ Partitioning of a graph into induced subgraphs not containing prescribed cliques ⋮ Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker ⋮ Polynomial treewidth forces a large grid-like-minor ⋮ Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs ⋮ A different short proof of Brooks' theorem ⋮ Finding independent transversals efficiently ⋮ Coloring Graphs with Dense Neighborhoods ⋮ Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph

Cites Work

• Unnamed Item
• Unnamed Item
• A condition for matchability in hypergraphs
• Independent systems of representatives in weighted graphs
• An upper bound for the chromatic number of line graphs
• A Note on Vertex List Colouring
• On hitting all maximum cliques with an independent set
• On the Strong Chromatic Number
• A Theorem on k-Saturated Graphs

This page was built for publication: Hitting all maximum cliques with a stable set using lopsided independent transversals