(\(\Delta-k\))-critical graphs (Q1767668): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Michael S. O. Molloy / rank | |||
Property / author | |||
Property / author: Bruce A. Reed / rank | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Property / author | |||
Property / author: Michael S. O. Molloy / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Bruce A. Reed / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
Property / cites work | |||
Property / cites work: Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5520564 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Small graphs with chromatic number 5: A computer search / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: 25 pretty graph colouring problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chromatic neighborhood sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3839005 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4250147 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Colouring graphs when the number of colours is nearly the maximum degree / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4242948 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A strengthening of Brooks' theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On critical subgraphs of colour-critical graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 19:37, 7 June 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