×

(\(\Delta-k\))-critical graphs. (English) Zbl 1062.05056

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 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 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.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Emden-Weinert, T.; Hougardy, S.; Kreuter, B., Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput., 7, 4, 375-386 (1998) · Zbl 0918.05051
[2] Gallai, T., Kritische Graphen II, Magyar Tud. Akad. Mat. Kutató Int. Közl., 8, 373-395 (1963), (in German) · Zbl 0144.23204
[3] Jensen, T.; Royle, G. F., Small graphs with chromatic number 5A computer search, J. Graph Theory, 19, 1, 107-116 (1995) · Zbl 0821.05023
[4] Jensen, T.; Toft, B., Graph Colouring Problems (1995), Wiley: Wiley New York · Zbl 0971.05046
[5] Molloy, M., Chromatic neighborhood set, J. Graph Theory, 31, 4, 303-311 (1999) · Zbl 0940.05028
[6] M. Molloy, B. Reed, Colouring graphs whose chromatic number is near their maximum degree, Proceedings of the Third Latin American Symposium on Theoretical Informatics (LATIN’98), 1998, pp. 216-225.; M. Molloy, B. Reed, Colouring graphs whose chromatic number is near their maximum degree, Proceedings of the Third Latin American Symposium on Theoretical Informatics (LATIN’98), 1998, pp. 216-225. · Zbl 0918.05053
[7] Molloy, M.; Reed, B., Graph Colouring and the Probabilistic Method (2001), Springer: Springer Berlin · Zbl 0926.05018
[8] M. Molloy, B. Reed, Colouring graphs when the number of colours is almost the maximum degree, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 462-470.; M. Molloy, B. Reed, Colouring graphs when the number of colours is almost the maximum degree, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 462-470. · Zbl 1323.05052
[9] Reed, B., \( \chi, \Delta \), and \(\omega \), J. Graph Theory, 27, 177-212 (1998) · Zbl 0980.05026
[10] Reed, B., A strengthening of Brooks’ Theorem, J. Combin. Theory (B), 76, 136-149 (1999) · Zbl 0935.05045
[11] G. Royle, Small graphs, In URL: http://www.cs.uwa.edu.au/ \( \sim;\); G. Royle, Small graphs, In URL: http://www.cs.uwa.edu.au/ \( \sim;\)
[12] Toft, B., Critical subgraphs of colour critical graphs, Discrete Math., 7, 377-392 (1974) · Zbl 0271.05112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.