When removing an independent set is optimal for reducing the chromatic number

DOI10.1016/j.ejc.2023.103781zbMath1525.05046arXiv2203.13833MaRDI QIDQ6057453

Stijn Cambie, John Haslegrave, Ross J. Kang

Publication date: 25 October 2023

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Brooks' theoremchromatic vertex stability number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

On the vertex stability numbers of graphs

Cites Work

• Unnamed Item
• Colouring graphs when the number of colours is almost the maximum degree
• A simplified NP-complete satisfiability problem
• (\(\Delta-k\))-critical graphs
• On the chromatic vertex stability number of graphs
• A Note on Vertex List Colouring
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Reducibility among Combinatorial Problems
• Hitting all maximum cliques with a stable set using lopsided independent transversals

This page was built for publication: When removing an independent set is optimal for reducing the chromatic number