Large cliques in graphs with high chromatic number

DOI10.1016/j.disc.2022.113181zbMath1529.05062OpenAlexW4297493701MaRDI QIDQ6091811

Penny E. Haxell, Colter MacDonald

Publication date: 27 November 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2022.113181

zbMATH Keywords

chromatic numbercliquemaximum degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• 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
• (\(\Delta-k\))-critical graphs
• A Note on Vertex List Colouring
• Graphs with $\chi=\Delta$ Have Big Cliques
• A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω
• Bounding χ in terms of ω and Δ for quasi-line graphs
• A Note On Reed's Conjecture
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs
• Coloring Claw-Free Graphs with $\Delta-1$ Colors
• A local epsilon version of Reed's conjecture