|
Abstract
|
The aim of this paper is to assert that the minimum number of colors to color a geographical map and the angle-sum of a triangle are twin invariants of the two-dimensional plane. Peter Tait proved in an 1880 paper that a bridgeless cubic plane graph G has a 4-face-coloring if and only if G has a 3-edge-coloring. We explore the edge coloring problem of cubic graphs in this paper by using the newly proposed complex coloring approach. The concept of variable edges is introduced in the complex coloring method; a proper coloring is achieved by completely eliminating all variables in a color configuration of a cubic graph. The specification of solvable conditions is based on the decomposition of the configuration into maximal two-colored cycles. The class of cubic graphs that do not have 3-edge coloring can be naturally identified by the proposed unsolvability condition. Furthermore, we also propose that a particular configuration, called generalized Petersen configuration, of a bridgeless cubic plane graph is always solvable; an immediate consequence of this proposition is the 3-edge-coloring theorem, or equivalently, the 4CT. Despite that this self-evident proposition has been verified by over one hundred thousand of instances generated by computer, we still don’t have a logical proof of this assertion. Comparing edge coloring with system of linear equations, we found that the proposition of solvability and the parallel postulate in Euclidean geometry share some common characteristics of the plane. Firstly, they both provide solvability conditions on equations in the plane. Secondly, the two basic invariants of the plane can be respectively deduced from the two postulates; namely the chromatic index of bridgeless cubic plane graphs and the sum of the angles in every triangle. The analogy between these two propositions not only reveals the significance of the concept of complex coloring in graph theory, but also hints that a logical proof of the proposition of solvability may be impossible. That is, from the histories of parallel postulate and 4CT, we tend to think that describing these fundamental characteristics by even more elementary properties of the plane is inconceivable.
|
|
Affiliation
|
李东教授，现任上海交通大学电子工程系致远讲席教授。自1977年获得纽约理工大学电子工程博士学位，他先后担任美国电话电报贝尔实验室研究员(1977-1983)，美国贝尔通讯实验室杰出研究员(1983-1993)，美国哥伦比亚大学电子工程系兼任副教授(1989-1991)，纽约理工大学电子工程系正教授(1991-1993)，香港中文大学信息工程系讲座教授(1993-2010)。
李教授的主要研究领域包括分组交换系统设计与分析，通讯系统性能分析，关系数据模型，发表论文80余篇，编著Principles of Broadband Switching and Networking一书，并拥有5项国际专利。李教授的工作获得IEEE Leonard G. Abraham Prize Paper Award，中国国家自然科学奖 (三等)，Outstanding Paper Award (IEICE, Japan)，Distinguished Member of Professional Staff (Bellcore) 等奖项。他现为IEEE Fellow，并担任IEEE Transaction on Communications 和 Journal of Communication and Network期刊的编辑
|
