Even triangulations of ³ and the coloring of graphs
Even triangulations of ³ and the coloring of graphs
复制标题
甚至 ³ 的三角剖分和图形的着色
DOI：
--
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
H. Onishi
中科院分区：
文献类型：
--
作者：
J. Goodman;H. Onishi
0. 简介。通过 Appel-Haken 对四色问题的解决方案 [2]，表征这些可 4 色的图形（无论是否为平面）的问题仍然悬而未决。本文通过为嵌入在 3 空间中的图的 4 色性提供新的标准，代表了朝着解决方案迈出的一步，该标准是由嵌入在平面中的图的 3 色性的类似标准提出的。主要结果是，3-球体 S 3 中的图是（顶点）4-可着色的，当且仅当它是 S3-1 的“偶数”三角剖分的 1-骨架的子复形，其中每条边都有偶数个与其关联的面。相应的低一维结果是众所周知的[4，定理7.4.3]。在?1中，我们提出了该理论的总结以及一些辅助结果，在?2中，我们提出了3维的并行理论。自从本文最初提交以来，Robert D. Edwards 遵循 P. Deligne、R. MacPherson 和 J. Morgan 的想法，宣布了主要结果的（独立）证明（参见Notices Amer. Math. Soc. 24 (1977), A-257）。史蒂夫·菲斯克 (Steve Fisk) 题为《几何着色理论》的一系列精美论文最近开始出现在《数学进展》中。 (24 (1977), 298-340, 等等)，也包含在某种程度上与我们的想法重叠的想法。我们对审稿人提出的关于加强论文阐述的有益建议表示感谢。
0. Introduction. With the Appel-Haken solution to the Four Color Problem [2], the question remains open of characterizing those graphs, planar or not, that are 4-colorable. This paper represents a step toward a solution by offering a new criterion for the 4-colorability of a graph embedded in 3-space, which was suggested by an analogous criterion for the 3-colorability of a graph embedded in the plane. The main result is that a graph in the 3-sphere S 3 is (vertex) 4-colorable if and only if it is a subcomplex of the 1-skeleton of an "even" triangulation of S3-one in which every edge has an even number of faces incident to it. The corresponding result one dimension lower is well known [4, Theorem 7.4.3]. In ?1, we present a summary of this theory with some auxiliary results, and in ?2 we present the parallel theory in 3 dimensions. Since the original submission of this paper, Robert D. Edwards has announced an (independent) proof of the main result, following an idea of P. Deligne, R. MacPherson, and J. Morgan (see Notices Amer. Math. Soc. 24 (1977), A-257). The beautiful sequence of papers by Steve Fisk entitled Geometric coloring theory, which has begun appearing still more recently in Advances in Math. (24 (1977), 298-340, et seqq.), also contains ideas which overlap ours to some extent. We express our gratitude to the referee for his helpful suggestions about tightening the exposition of the paper.