On the connection between chromatic number, maximal clique and minimal degree of a graph
type: Item
instance of: scholarly article
title: On the connection between chromatic number, maximal clique and minimal degree of a graph
zbMATH Open document ID: 0284.05106
DOI: 10.1016/0012-365X(74)90133-2
author: B. Andrasfai
author: Vera T. Sós
author: P. Erdős
published in: Discrete Mathematics
publication date: 1974-01-01T00:00:00Z
review text: A well known theorem due to Brooks can be stated as: For \(r \geq 4\), any graph \(G\) has at most 2 of the following properties: (1) \(K_r\) is not contained in \(G\). (2) The chromatic number of \(G\) is at least \(r\). (3) The maximum degree of \(G\) is at most \(r-1\). In this paper the following analogue of Brooks' Theorem is proved via a sequence of lemmas: For \(r \geq 3\), any graph \(G\) with \(n\) vertices has at most two of the following properties: (4) \(K_r\) is not contained in \(G\). (5) The chromatic number of \(G\) is at least \(r\). (6) The minimum degree of \(G\) is greater than \(((3r-7)/(3r-4))n\). The authors also show that if \((3r-4)\) divides \(n\), then there exists a unique graph \(G\) of order \(n\) such that (4) and (5) hold, but the minimum degree of \(G\) is \(((3r-7)/(3r-4))n\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3445276
Wikidata QID: Q105583523
reviewed by: John Mitchem
MaRDI profile type: Publication
cites work: Graphentheoretische Extremalprobleme
cites work: On a theorem of Rademacher-Turán
cites work: Sur les relations symétriques dans l'ensemble fini
full work available at URL: 0012-365x(74)90133-2
OpenAlex ID: W2168685161
description: scientific article; zbMATH DE number 3445276