Graphs with chromatic number close to maximum degree

DOI10.1016/J.DISC.2011.12.014MaRDI QIDQ409481zbMATH OpenOpenAlexFDO

Authors Landon Rabern, Michael Stiebitz, Alexandr 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

Brooks' theoremcritical graphsgraph coloring

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1189240
• Distance graphs with maximum chromatic number
• Distance graphs with maximum chromatic number
• Colouring graphs when the number of colours is almost the maximum degree
• Colouring graphs when the number of colours is nearly the maximum degree
• The total chromatic number of graphs having large maximum degree
• scientific article; zbMATH DE number 798659
• scientific article; zbMATH DE number 3882454
• scientific article; zbMATH DE number 4177084
• Chromatic numbers in some graphs

Cites work

• \(\Delta \)-critical graphs with small high vertex cliques
• Another bound on the chromatic number of a graph
• Extremal graph packing problems: Ore-type versus Dirac-type
• scientific article; zbMATH DE number 3851121 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Note on the colouring of graphs
• Ore-type versions of Brooks' theorem
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• The structure of k-chromatic graphs

Cited in

(18)

• Sharpening an ore-type version of the Corrádi-Hajnal theorem
• Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• Graphs with \(\chi=\Delta\) have big cliques
• On the Corrádi-Hajnal theorem and a question of Dirac
• On graphs having prescribed clique number, chromatic number, and maximum degree
• Graph coloring approach with new upper bounds for the chromatic number: team building application
• Ore's conjecture on color-critical graphs is almost true
• scientific article; zbMATH DE number 7666240 (Why is no real title available?)
• 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
• On chromatic number and clique number in \(k\)-step Hamiltonian graphs
• Partitioning of a graph into induced subgraphs not containing prescribed cliques
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Characterizing 4-critical graphs with Ore-degree at most seven
• Cliques and high odd holes in graphs with chromatic number equal to maximum degree
• Stochastic solutions for fractional wave equations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409481)