| 外平面图的弱完备染色 |
| |
| 引用本文： | 陈敏,杨建民,张豪,王依婷. 外平面图的弱完备染色[J]. 运筹学学报, 2021, 25(1): 132-136. DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.013 |
| |
| 作者姓名： | 陈敏 杨建民 张豪 王依婷 |
| |
| 作者单位： | 1. 浙江师范大学数学与计算机科学学院, 浙江 金华 321004 |
| |
| 基金项目： | 国家自然科学基金(No.11971437);浙江省自然科学基金(No.LY19A010015)。 |
| |
| 摘 要： | 假设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的最小值，记成χvef（G）。2016年，Fabrici等人猜想：每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想，即外平面图是弱完备7-可染的。
|
| 关 键 词： | 扇形图 外平面图 弱完备染色 弱完备色数 最大度 |
| 收稿时间： | 2019-09-06 |
Weakly entire coloring of outerplanar graphs |
| |
| CHEN Min,YANG Jianmin,ZHANG Hao,WANG Yiting. Weakly entire coloring of outerplanar graphs[J]. OR Transactions, 2021, 25(1): 132-136. DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.013 |
| |
| Authors: | CHEN Min YANG Jianmin ZHANG Hao WANG Yiting |
| |
| Affiliation: | 1. Department of Mathematics, Zhejiang NormalUniversity, Jinhua 321004, Zhejiang, China |
| |
| 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 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 Xvef(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. |
| |
| Keywords: | fan graph outerplanar graph weakly entire coloring weakly entire chromatic number maximum degree |
| 本文献已被 维普 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
|
