外平面图的弱完备染色

展开
  • 1. 浙江师范大学数学与计算机科学学院, 浙江 金华 321004
陈敏 E-mail: chenmin@zjnu.cn

收稿日期: 2019-09-06

  网络出版日期: 2021-03-05

基金资助

国家自然科学基金(11971437);浙江省自然科学基金(LY19A010015)

Weakly entire coloring of outerplanar graphs

Expand
  • 1. Department of Mathematics, Zhejiang NormalUniversity, Jinhua 321004, Zhejiang, China

Received date: 2019-09-06

  Online published: 2021-03-05

摘要

假设G=(VEF)是一个平面图。如果e1e2G中两条相邻边且在关联的面的边界上连续出现,那么称e1e2面相邻。图G的一个弱完备k-染色是指存在一个从VEFk色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及VEF中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χvefG)。2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。

本文引用格式

陈敏, 杨建民, 张豪, 王依婷 . 外平面图的弱完备染色[J]. 运筹学学报, 2021 , 25(1) : 132 -136 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.013

Abstract

Let G=(V, E, F) be a plane graph. If e1 and e2 are consecutively adjacent with the same face, then we say that e1 and e2 are facially adjacent. A plane graph G is called weakly entire k-colorable if there is a mapping from VEF to {1, …, K} such that any facially adjacent edges, adjacent vertices, adjacent faces, and any two incident elements in VEF receive distinct colors. The weakly entire chromatic number, denoted χvef(G), of G is defined to be the least integer k such that G is weakly entire k-colorable. In 2016, Fabrici et al. conjectured that every connected, loopless, bridgeless plane graph is weakly entire 7-colorable. In this paper, we prove that the conjecture is true for outerplanar graphs. Namely, outerplanar graphs are weakly entire 7-colorable.

参考文献

1 Kronk H , Mitchem J . A seven-color theorem on the sphere[J]. Discrete Mathematics, 1973, 5 (1): 253- 260.
2 Borodin O V . On the total coloring of planar graphs[J]. Journal für die reine und angewandte Mathematik, 1989, 394 (1): 180- 185.
3 Borodin O V . Structural theorem on plane graphs with application tothe entire coloring number[J]. Journal of Graph Theory, 1996, 23 (3): 233- 239.
4 Sanders D P , Zhao Y . On the entire coloring conjecture[J]. Canadian Mathematical Bulletin, 2000, 43 (1): 108- 114.
5 Wang W , Zhu X . Entire colouring of plane graphs[J]. Journal of Combinatorial Theory Series B, 2011, 101 (6): 490- 501.
6 Fabrici I , Jendrol S , Vrbjarova M . Facial entire colouring of planegraphs[J]. Discrete Mathematics, 2016, 339 (2): 626- 631.
7 Chen M , Fan Y , Wang Y , et al. A sufficient condition for planargraphs to be (3, 1)-choosable[J]. Journal of Combinatorial Optimization, 2017, 34 (4): 987- 1011.
8 Chen M , Raspaud A , Wang W . Plane graphs with maximum degree 6 areedge-face 8-colorable[J]. Graphs & Combinatorics, 2014, 30 (4): 861- 874.
9 Cai J S , Wang J H , Zhang X . Restricted Colorings of Graphs[M]. Beijing: Science Press, 2019.
10 Bondy J. Murty U. Graph Theory[M]. New York: Springer, 2008.
11 Wang W F . On complete colouring of outerplanar graph[J]. Journal ofLiaoning University, 1992, 19 (1): 16- 21.
12 Wang W F . Edge-face entire chromatic number of outerplanar graphs[J]. Journal of Liaoning University, 1994, 21 (4): 1- 9.
文章导航

/