哈林图的弱点边染色

发布时间：2023-06-05 03:09

　　假设e1和e2是两条相邻边,若它们关联同一个面且在该面的边界上连续出现,则称e1和e2是面相邻的.平面图G是弱点边k-可染的是指存在映射π:V (G)∪E(G)→{1,···, k},使得任意两个相邻的顶点,任意两条面相邻的边,以及任意两个相关联的顶点和边都染不同的颜色.文中利用数学归纳法证明了:哈林图(Halin graph)是弱点边5-可染的,并给出可达到上界5的例子.

【文章页数】：5 页


本文编号：3831568