Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-01-09T21:51:31.808Z Has data issue: false hasContentIssue false
  • English
  • Français

Effective coloration

Published online by Cambridge University Press:  12 March 2014

Dwight R. Bean
Dwight R. Bean*
Affiliation:
University of San Diego, San Diego, California 92110
Get access Rights & Permissions [Opens in a new window]

Abstract

We are concerned here with recursive function theory analogs of certain problems in chromatic graph theory. The motivating question for our work is: Does there exist a recursive (countably infinite) planar graph with no recursive 4-coloring? We obtain the following results: There is a 3-colorable, recursive planar graph which, for all k, has no recursive k-coloring; every decidable graph of genus p ≥ 0 has a recursive 2(x(p) − 1)-coloring, where x(p) is the least number of colors which will suffice to color any graph of genus p; for every k ≥ 3 there is a k-colorable, decidable graph with no recursive k-coloring, and if k = 3 or if k = 4 and the 4-color conjecture fails the graph is planar; there are degree preserving correspondences between k-colorings of graphs and paths through special types of trees which yield information about the degrees of unsolvability of k-colorings of graphs.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 2 , June 1976 , pp. 469 - 480
Copyright
Copyright © Association for Symbolic Logic 1976

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

This material is part of a thesis submitted to the University of California at San Diego in June, 1973. The author wishes to acknowledge the many helpful ideas and the continuing encouragement of his advisor, Professor Alfred B. Manaster. He is also grateful for the referee's many constructive suggestions and corrections.

References

BIBLIOGRAPHY

[1] Chartrand, G. and Geller, D., Uniquely colorable planar graphs, Journal of Combinatorial Theory, vol. 6 (1969), pp. 271–278.CrossRefGoogle Scholar
[2] Greenwell, D., Semi-uniquely n-colorable graphs, Proceedings of the Second Louisiana Conference in Combinatorics, Graph Theory and Computing, University of Manitoba, Winnipeg, 1972.Google Scholar
[3] Jockusch, C., Ramsey's theorem and recursion theory, this Journal, vol. 37 (1972), pp. 268–280.Google Scholar
[4] Jockusch, C. and Soare, R., Π0 1 classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[5] Jockusch, C. and Soare, R., Degrees of members of Π0 1 classes, Pacific Journal of Mathematics, vol. 40 (1972), pp. 605–616.CrossRefGoogle Scholar
[6] Karp, R. M., Reducibility among combinatorial problems, Complexity of computer computations (Miller, and Thatcher, , Editors), Plenum Press, New York, 1972.Google Scholar
[7] Kreisel, G. and Krivine, J., Elements of mathematical logic, North-Holland, Amsterdam, 1967.Google Scholar
[8] Manaster, A. and Rosenstein, J., Effective matchmaking, Proceedings of the London Mathematical Society, vol. 25 (1972), pp. 615–654.CrossRefGoogle Scholar
[9] Manaster, A. and Rosenstein, J., Effective matchmaking and k-chromatic graphs, Proceedings of the American Mathematical Society, vol. 39 (1973), pp. 371–378.Google Scholar
[10] Ore, O., The four-color problem, Academic Press, New York, 1967.Google Scholar
[11] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[12] Specker, E., Ramsey's theorem does not hold in recursive set theory, Logic Colloquium 69 (Gandy, R. and Yates, C., Editors), North-Holland, Amsterdam, 1971.Google Scholar
[13] Stockmeyer, L., Planar 3-colorability is polynomial complete, SIGACT News, 07 1973, pp. 19–26.Google Scholar