哈林图的弱边面染色

作者：余梦蕾^*; 陈敏^*

来源：数学进展, 2018, 47(04): 509-516.

• 哈林图
• 轮图
• 弱边面染色
• 弱边面色数

设G=(V,E,F)是一个无环的连通平面图,其中V表示点集,E表示边集,F表示面集.对于任意的两条相邻边e1和e2,如果它们关联同一个面且在该面的边界上连续出现,那么称e1和e2是面相邻的.图G是弱边面k-可染的是指存在一个映射π:EUF→{1,2,…,k},使得任意两个相关联的边和面,任意两个相邻的面,以及任意两条面相邻的边都染不同的颜色.平面图G的弱边面染色数是指G是弱边面k-可染的数k的最小值,用ef(G)表示.2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文我们给出此猜想的一个充分条件,即证明:哈林图是弱边面5-可染的,其中上界5是最好可能的.

• 单位
  浙江师范大学