{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1306303","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1306303","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q1306303","kernelVersion":"v1","immutable":true,"modified":"2025-12-25T17:27:22Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q1306303","name":"A strengthening of Brooks' theorem","headline":"A strengthening of Brooks' theorem","description":"scientific article; zbMATH DE number 1346955","url":"https://portal.mardi4nfdi.de/entity/Q1306303","datePublished":"1999-12-20","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q661944"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q256978"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1006/JCTB.1998.1891","url":"https://doi.org/10.1006/JCTB.1998.1891"},"sameAs":["https://doi.org/10.1006/JCTB.1998.1891"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q4004078"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2533119"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3216674"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1229732"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5782525"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4074927"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4857375"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3909076"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1354718"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1297726"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4250147"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3839005"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4242948"}]},"provenance":{"prov:generatedAtTime":"2025-12-25T17:27:22Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}