Ore-type versions of Brooks' theorem

DOI10.1016/j.jctb.2008.06.007zbMath1198.05059OpenAlexW2150871094MaRDI QIDQ1003831

Henry A. Kierstead, Alexandr V. Kostochka

Publication date: 4 March 2009

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2008.06.007

zbMATH Keywords

graph coloringBrooks' theoremequitable coloringedge degree

Mathematics Subject Classification ID

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

Related Items (16)

Ramsey number of paths and connected matchings in Ore-type host graphs ⋮ On the Corrádi-Hajnal theorem and a question of Dirac ⋮ Graphs containing every 2-factor ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Sharpening an ore-type version of the Corrádi-Hajnal theorem ⋮ Graphs with chromatic number close to maximum degree ⋮ Ramsey-Turán type results for matchings in edge colored graphs ⋮ Ore's conjecture on color-critical graphs is almost true ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Characterizing 4-critical graphs with Ore-degree at most seven ⋮ Unnamed Item ⋮ A fast algorithm for equitable coloring ⋮ Improved lower bounds on the number of edges in list critical and online list critical graphs ⋮ Partitioning 2-Edge-Colored Ore-Type Graphs by Monochromatic Cycles ⋮ Equitable defective coloring of sparse planar graphs ⋮ \(\Delta \)-critical graphs with small high vertex cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equitable versus nearly equitable coloring and the Chen-Lih-Wu Conjecture
• On equitable \(\Delta\)-coloring of graphs with low average degree
• Spanning subgraphs of random graphs
• Almost \(H\)-factors in dense graphs
• Colorings and orientations of graphs
• Proof of the Seymour conjecture for large graphs
• Equitable coloring and the maximum degree
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• On equitable coloring of bipartite graphs
• \(H\)-factors in dense graphs
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• An Ore-type theorem on equitable coloring
• Note on Hamilton Circuits
• Ore-type graph packing problems
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• The infamous upper tail
• Some Theorems on Abstract Graphs

This page was built for publication: Ore-type versions of Brooks' theorem