A strengthening of Brooks' theorem (Q1306303)

From MaRDI portal
Revision as of 11:38, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
A strengthening of Brooks' theorem
scientific article

    Statements

    A strengthening of Brooks' theorem (English)
    0 references
    0 references
    20 December 1999
    0 references
    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.
    0 references
    chromatic number
    0 references
    colouring
    0 references
    clique
    0 references

    Identifiers