关于一个猜想的简单证明  

A Simple Proof of a Conjecture

作　　者：苗莲英[1] 陈东灵 逄世友[1] 

机构地区：[1]山东农业大学基础部

出　　处：《山东矿业学院学报》1998年第1期89-91,共3页Journal of Shandong University of Science and Technology(Natural Science)

摘　　要：图Ｇ的一个（正常）路着色是一映射φ：Ｖ（Ｇ）→Ｃ，使得Ｃ中任一元素的原象的导出子图是路的不交并，使Ｇ有正常路着色所需要的Ｃ的最小基数｜Ｃ｜，称为Ｇ的路色数，用ｘ（Ｇ；Ｐ∞）表示。Ｊ．Ａｋｉｙａｍａ和Ｅｒａ［３］提出如下问题：是否存在平面图Ｇ使得ｘ（Ｇ；Ｐ∞）＝４？关于这一问题，已有人证明［３，５］；对于任意平面图Ｇ，都有ｘ（Ｇ；Ｐ∞）≤３。A proper path-coloring of a graph G is a mapping of V(G) onto the set C of colors such that the induced subgraph of the resource images of every eiement in C is a diojoint union of phths. The phth-chromatic number of a graph G, denoted by x(G;P∞), is the least cardinal number of C for which there exists a proper path-coloring of G. J.Akiyama and H.Era posed the following conjecture: if there exists a planar graph G such that x(G;P∞)=4? About this problem, someone has proved, that is for any planar graph G, x(G;P∞)≤3. In section two, we give a simpler new proof of the conjecture in the sense of path-chromatic number.

关 键 词：平面图 路色数 平面三角剖分图 猜想 证明 

分 类 号：O157.5[理学—数学]