Effective coloration
Effective coloration
复制标题
有效着色
DOI：
10.1017/s0022481200051549
复制
发表时间：
1976
影响因子：
0.6
通讯作者：
Dwight R. Bean
中科院分区：
文献类型：
--
作者：
Dwight R. Bean
本文主要研究色图论中某些问题的递归函数论类似物。我们工作的动机问题是：是否存在一个递归（可数无限）平面图没有递归4-着色？我们得到了如下结果：存在一个3-可着色的递归平面图，对所有k，它没有递归k-着色;亏格p ≥ 0的每一个可判定图都有递归2（x（p）-1）-着色，其中x（p）是亏格p的最少着色数;对任意k ≥ 3，存在一个k-可着色可判定图，且无递归k-着色，且若k = 3或k = 4且四色猜想不成立，则该图是平面图;在图的k-着色和通过特殊类型的树的路径之间存在度保持对应，其产生关于图的k-着色的不可解度的信息。
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.