TRIANGULATIONS OF S 3 AND THE COLORING OF GRAPHS-猫眼课题宝

S 3 的三角剖分和图形的着色

DOI：

发表时间：

2010

期刊：

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

H. Onishi

给出了一个简单的充分必要条件，使图的顶点（无论是平面的还是非平面的）都具有正确的四色性。该准则涉及 S3 的“偶数”三角剖分的概念，并以自然的方式概括了平面图三色性的相应准则。 0. 简介。通过 Appel-Haken 对四色问题的解决方案 [2]，表征这些可 4 色的图形（无论是否为平面）的问题仍然悬而未决。本文通过为嵌入在 3 空间中的图的 4 色性提供新的标准，代表了朝着解决方案迈出的一步，该标准是由嵌入在平面中的图的 3 色性的类似标准提出的。主要结果是，3-球体 S3 中的图是（顶点）4-可着色的，当且仅当它是 S^-one 的“偶数”三角剖分的 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, 等等)，也包含在某种程度上与我们的想法重叠的想法。我们对审稿人提出的关于加强论文阐述的有益建议表示感谢。编辑于 1977 年 1 月 3 日收到，并于 1977 年 10 月 25 日和 1978 年 4 月 24 日修订。AMS (MOS) 学科分类 (1970)。初级05C15；次级 05C10、55A15。 © 美国数学会 1979

A simple necessary and sufficient condition is given for the vertices of a graph, planar or not, to be properly four-colorable. This criterion involves the notion of an "even" triangulation of S3 and generalizes, in a natural way, a corresponding criterion for the three-colorability of planar graphs. 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 S3 is (vertex) 4-colorable if and only if it is a subcomplex of the 1-skeleton of an "even" triangulation of S^-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. Received by the editors January 3, 1977 and, in revised form, October 25, 1977 and April 24, 1978. AMS (MOS) subject classifications (1970). Primary 05C15; Secondary 05C10, 55A15. © American Mathematical Society 1979

TRIANGULATIONS OF S 3 AND THE COLORING OF GRAPHS

S 3 的三角剖分和图形的着色

文献摘要

被引文献

相似文献