Colouring a graph frugally
type: Item
instance of: scholarly article
title: Colouring a graph frugally
zbMATH Open document ID: 0910.05023
DOI: 10.1007/BF01195001
author: Hugh Hind
author: Michael Molloy
author: Bruce Reed
published in: Combinatorica
publication date: 1999-03-14T00:00:00Z
review text: Every graph with maximum degree \(\Delta\geq\Delta_0\) has a proper \((\Delta+1)\)-coloring in which every color class has at most \(\log^8\Delta\) elements in the neighborhood of any vertex. If \(\beta\geq 1\) and the maximum degree is \(\delta\geq\Delta_\beta\) then there is a \(\max((\beta+1)\Delta,e^3\Delta^{1+{1\over\beta}})\)-coloring in which every color class has at most \(\beta\) elements in the neighborhood of any vertex. An example of Noga Alon gives that this is essentially best possible.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1261163
zbMATH Keywords: graph colorings
zbMATH Keywords: Lovász local lemma
zbMATH Keywords: probabilistic methods
reviewed by: Péter Komjáth
MaRDI profile type: Publication
cites work: A parallel algorithmic version of the local lemma
cites work: An algorithmic approach to the Lovász local lemma. I
cites work: Q5512461
full work available at URL: https://doi.org/10.1007/bf01195001
OpenAlex ID: W2024071264
description: scientific article; zbMATH DE number 1261163