(\(\Delta-k\))-critical graphs (Q1767668): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jctb.2004.09.006 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1968677127 / rank | |||
Normal rank |
Revision as of 02:14, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | (\(\Delta-k\))-critical graphs |
scientific article |
Statements
(\(\Delta-k\))-critical graphs (English)
0 references
8 March 2005
0 references
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.
0 references
critical graph
0 references
colouring
0 references
probabilistic method
0 references
chromatic number
0 references
maximum degree
0 references