(\(\Delta-k\))-critical graphs
type: Item
instance of: scholarly article
title: (\(\Delta-k\))-critical graphs
zbMATH Open document ID: 1062.05056
author: Babak Farzad
author: Michael Molloy
author: Bruce Reed
published in: Journal of Combinatorial Theory. Series B
publication date: 2005-03-08T00:00:00Z
review text: The paper contains a characterisation of \((\Delta-2),(\Delta-3), (\Delta-4)\) and \((\Delta-5)\)-colourable graphs for a sufficiently large value of \(\Delta\) (where \(\Delta\) is the maximum degree of a graph). These results extend a classical result of \textit{R. L. Brooks} [Proc. Camb. Philos. Soc. 37, 194--197 (1941; Zbl 0027.26403)] on \(\Delta\) and \(\Delta+1\)-colourable graphs and a characterisation of \(\Delta-1\)-colourable graphs by \textit{B. Reed} [J. Comb. Theory, Ser. B 76, 136--149 (1999; Zbl 0935.05045)]. Moreover a linear time algorithm for checking the \((\Delta-k)\)-colourability, for sufficiently large \(\Delta\) and any constant \(k\), is provided.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2142247
zbMATH Keywords: critical graph
zbMATH Keywords: colouring
zbMATH Keywords: probabilistic method
zbMATH Keywords: chromatic number
zbMATH Keywords: maximum degree
reviewed by: Gabriel Semanišin
MaRDI profile type: Publication
full work available at URL: j.jctb.2004.09.006
OpenAlex ID: W1968677127
cites work: Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
cites work: Q5520564
cites work: Small graphs with chromatic number 5: A computer search
cites work: 25 pretty graph colouring problems
cites work: Chromatic neighborhood sets
cites work: Q3839005
cites work: Q4250147
cites work: Colouring graphs when the number of colours is nearly the maximum degree
cites work: Q4242948
cites work: A strengthening of Brooks' theorem
cites work: On critical subgraphs of colour-critical graphs
DOI: 10.1016/J.JCTB.2004.09.006
description: scientific article; zbMATH DE number 2142247