A strengthening of Brooks' theorem
type: Item
instance of: scholarly article
title: A strengthening of Brooks' theorem
zbMATH Open document ID: 0935.05045
published in: Journal of Combinatorial Theory. Series B
publication date: 1999-12-20T00:00:00Z
review text: This paper mainly proves the conjecture due to \textit{A. Beutelspacher} and \textit{P.-R. Hering} [Ars Comb. 18, 201-216 (1984; Zbl 0554.05025)]. More precisely, the author proves that for sufficiently large \(\Delta\), any graph with maximum degree at most \(\Delta\) and no cliques of size \(\Delta\) has a \(\Delta-1\) colouring. The proof relies on the fact that if \(G\) is a minimal counterexample to the result, then any reasonably dense set of about \(\Delta\) vertices in \(G\) is either a clique or the intersection of two cliques.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1346955
zbMATH Keywords: chromatic number
zbMATH Keywords: colouring
zbMATH Keywords: clique
author: Bruce Reed
reviewed by: Bai Kishan Dass
MaRDI profile type: Publication
full work available at URL: jctb.1998.1891
OpenAlex ID: W2011731192
cites work: Q4004078
cites work: Weighted sums of certain dependent random variables
cites work: Q3216674
cites work: On an upper bound of the graph's chromatic number, depending on the graph's degree and density
cites work: Q5782525
cites work: Q4074927
cites work: Q4857375
cites work: Q3909076
cites work: A bound on the strong chromatic index of a graph
cites work: A bound on the total chromatic number
cites work: Q4250147
cites work: Q3839005
cites work: Q4242948
DOI: 10.1006/JCTB.1998.1891
description: scientific article; zbMATH DE number 1346955