Geodesic
The Effective Version of Brooks' Theorem
Canadian journal of mathematics, Tome 34 (1982) no. 5, pp. 1036-1046

Voir la notice de l'article provenant de la source Cambridge University Press

One of the fundamental results on graph coloring is the following classical theorem of Brooks.BROOKS’ THEOREM. Suppose that k ≧ 3 and that G is a k-regular graph which does not induce a (k + 1)-clique. Then G is k-colorable.Brooks proved his theorem in [1]; several more recent proofs have appeared in [3], [4] and [5]. All the proofs of this theorem have the common feature of applying only to finite graphs; the transition to infinite graphs can be accomplished by a very standard implementation of the Compactness Theorem (or some other equally noneffective device such as the theorem of deBruijn and Erdös [2] asserting that a graph is k-colorable if and only if each of its finite subgraphs is). Thus, it is not immediately apparent that an effective version of Brooks’ Theorem exists. It is our purpose to show, however, that the effective analogue of Brooks' Theorem is indeed true. 
Schmerl, James H. The Effective Version of Brooks' Theorem. Canadian journal of mathematics, Tome 34 (1982) no. 5, pp. 1036-1046. doi: 10.4153/CJM-1982-075-6
@article{10_4153_CJM_1982_075_6,
     author = {Schmerl, James H.},
     title = {The {Effective} {Version} of {Brooks'} {Theorem}},
     journal = {Canadian journal of mathematics},
     pages = {1036--1046},
     year = {1982},
     volume = {34},
     number = {5},
     doi = {10.4153/CJM-1982-075-6},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-075-6/}
}
TY  - JOUR
AU  - Schmerl, James H.
TI  - The Effective Version of Brooks' Theorem
JO  - Canadian journal of mathematics
PY  - 1982
SP  - 1036
EP  - 1046
VL  - 34
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-075-6/
DO  - 10.4153/CJM-1982-075-6
ID  - 10_4153_CJM_1982_075_6
ER  - 
%0 Journal Article
%A Schmerl, James H.
%T The Effective Version of Brooks' Theorem
%J Canadian journal of mathematics
%D 1982
%P 1036-1046
%V 34
%N 5
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-075-6/
%R 10.4153/CJM-1982-075-6
%F 10_4153_CJM_1982_075_6

[1] 1. Brooks, R. L., On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197./ Google Scholar

[2] 2. deBruijn, N. G. and Erdos, P., A colour problem for infinite graphs and a problem in the theory of relations, Kon. Ned. Akad. Wetensch. Proc, Ser. A 5/+ (1951), 371–373./ Google Scholar

[3] 3. Lovâsz, L., Three short proofs in graph theory, J. Comb. Th. (B) 19 (1975), 269–271./ Google Scholar

[4] 4. Melnikov, L. S. and Vizing, V. G., A new proof of Brooks’ Theorem, J. Comb. Th. 7 (1969), 289–290./ Google Scholar

[5] 5. Ponstein, H., A new proof of Brooks’ chromatic number theorem for graphs, J. Comb. Th. 7 (1969), 255–257./ Google Scholar

[6] 6. Rogers, H. Jr., Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967./ Google Scholar

[7] 7. Schmerl, J. H., Recursive colorings of graphs. Can. J. Math. 32 (1980), 821–830./ Google Scholar

Cité par Sources :