Graphs with $\chi=\Delta$ Have Big Cliques

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

zbMATH Keywords

graph coloringBrooks' theoremBorodin-Kostochka conjecturehigh degree subgraph

Mathematics Subject Classification ID

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