A strengthening of Brooks' theorem

DOI10.1006/jctb.1998.1891zbMath0935.05045OpenAlexW2011731192MaRDI QIDQ1306303

Bruce A. Reed

Publication date: 20 December 1999

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

Full work available at URL: https://doi.org/10.1006/jctb.1998.1891

zbMATH Keywords

colouringchromatic numberclique

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (29)

Ramsey-nice families of graphs ⋮ Brooks' Theorem and Beyond ⋮ List-Coloring Claw-Free Graphs with $\Delta-1$ Colors ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ A note on \(\Delta\)-critical graphs ⋮ The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs ⋮ Large cliques in graphs with high chromatic number ⋮ The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree ⋮ Special issue in honour of Landon Rabern ⋮ Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors ⋮ Strengthening Brooks' chromatic bound on \(P_6\)-free graphs ⋮ Borodin-Kostochka conjecture holds for odd-hole-free graphs ⋮ Coloring hammer-free graphs with \(\Delta - 1\) colors ⋮ Partitioning of a graph into induced subgraphs not containing prescribed cliques ⋮ On the Grundy and \(b\)-chromatic numbers of a graph ⋮ Unnamed Item ⋮ Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker ⋮ Asymptotically optimal frugal colouring ⋮ Chromatic numbers of layered graphs with a bounded maximal clique ⋮ Dynamic proper colorings of a graph ⋮ (\(\Delta-k\))-critical graphs ⋮ On the Grundy Number of a Graph ⋮ Algorithmic bounds for the chromatic number† ⋮ The distance coloring of graphs ⋮ Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs ⋮ Coloring Graphs with Dense Neighborhoods ⋮ A note on coloring vertex-transitive graphs

Cites Work

• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• A bound on the total chromatic number
• A bound on the strong chromatic index of a graph
• Weighted sums of certain dependent random variables
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A strengthening of Brooks' theorem