运筹学学报 >
2021 , Vol. 25 >Issue 1: 132 - 136
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.01.013
外平面图的弱完备染色
收稿日期: 2019-09-06
网络出版日期: 2021-03-05
基金资助
国家自然科学基金(11971437);浙江省自然科学基金(LY19A010015)
Weakly entire coloring of outerplanar graphs
Received date: 2019-09-06
Online published: 2021-03-05
假设G=(V,E,F)是一个平面图。如果e1和e2是G中两条相邻边且在关联的面的边界上连续出现,那么称e1和e2面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成
陈敏, 杨建民, 张豪, 王依婷 . 外平面图的弱完备染色[J]. 运筹学学报, 2021 , 25(1) : 132 -136 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.013
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 V ∪ E ∪ F to {1, …, K} such that any facially adjacent edges, adjacent vertices, adjacent faces, and any two incident elements in V ∪ E ∪ F receive distinct colors. The weakly entire chromatic number, denoted
| 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. |
/
| 〈 |
|
〉 |