Graphs with chromatic number close to maximum degree

DOI10.1016/J.DISC.2011.12.014zbMATH Open1270.05043OpenAlexW2032656190MaRDI QIDQ409481FDOQ409481

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

graph coloringBrooks' theoremcritical graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• \(\Delta \)-critical graphs with small high vertex cliques

Cited In (17)

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

Recommendations

• The total chromatic number of graphs having large maximum degree 👍 👎
• 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 👍 👎
• Chromatic numbers in some graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)