Graphs with $\chi=\Delta$ Have Big Cliques
From MaRDI portal
Publication:2949718
DOI10.1137/130929515zbMath1321.05080arXiv1305.3526OpenAlexW1837258853MaRDI QIDQ2949718
Daniel W. Cranston, Landon Rabern
Publication date: 2 October 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.3526
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)
Related Items (11)
Painting squares in \(\Delta^2-1\) shades ⋮ List-Coloring Claw-Free Graphs with $\Delta-1$ Colors ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ A note on \(\Delta\)-critical graphs ⋮ Large cliques in graphs with high chromatic number ⋮ The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree ⋮ Partitioning of a graph into induced subgraphs not containing prescribed cliques ⋮ Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices ⋮ Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker ⋮ Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs ⋮ A note on coloring vertex-transitive graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graphs with chromatic number close to maximum degree
- Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
- List colouring when the chromatic number is close to the order of the graph
- \(\Delta \)-critical graphs with small high vertex cliques
- Ore-type versions of Brooks' theorem
- Three short proofs in graph theory
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- Another bound on the chromatic number of a graph
- A strengthening of Brooks' theorem
- Probabilistic methods in coloring and decomposition problems
- Partitioning and coloring graphs with degree constraints
- On the choosability of complete multipartite graphs with part size three
- Variable degeneracy: Extensions of Brooks' and Gallai's theorems
- A note on coloring vertex-transitive graphs
- A Note on Vertex List Colouring
- On hitting all maximum cliques with an independent set
- A Sharper Local Lemma with Improved Applications
- A constructive proof of the general lovász local lemma
- Hitting all maximum cliques with a stable set using lopsided independent transversals
- Coloring Claw-Free Graphs with $\Delta-1$ Colors
- A Note on Hitting Maximum and Maximal Cliques With a Stable Set
- A Theorem on k-Saturated Graphs
- Coloring Graphs with Dense Neighborhoods
This page was built for publication: Graphs with $\chi=\Delta$ Have Big Cliques
