Graphs with chromatic number close to maximum degree

DOI10.1016/J.DISC.2011.12.014zbMath1270.05043OpenAlexW2032656190MaRDI QIDQ409481

Michael Stiebitz, Landon Rabern, Alexandr V. Kostochka

Publication date: 13 April 2012

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

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

zbMATH Keywords

graph coloringcritical graphsBrooks' theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (15)

On the Corrádi-Hajnal theorem and a question of Dirac ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Sharpening an ore-type version of the Corrádi-Hajnal theorem ⋮ A note on Reed's conjecture for triangle-free graphs ⋮ Special issue in honour of Landon Rabern ⋮ Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors ⋮ Partitioning of a graph into induced subgraphs not containing prescribed cliques ⋮ Unnamed Item ⋮ Graph coloring approach with new upper bounds for the chromatic number: team building application ⋮ Unnamed Item ⋮ Ore's conjecture on color-critical graphs is almost true ⋮ Characterizing 4-critical graphs with Ore-degree at most seven ⋮ Improved lower bounds on the number of edges in list critical and online list critical graphs ⋮ Stochastic solutions for fractional wave equations ⋮ Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs

Cites Work

• \(\Delta \)-critical graphs with small high vertex cliques
• Ore-type versions of Brooks' theorem
• Another bound on the chromatic number of a graph
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• Note on the colouring of graphs
• The structure of k-chromatic graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Graphs with chromatic number close to maximum degree