首页 | 本学科首页   官方微博 | 高级检索  
     

外平面图的弱完备染色
引用本文:陈敏,杨建民,张豪,王依婷. 外平面图的弱完备染色[J]. 运筹学学报, 2021, 25(1): 132-136. DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.013
作者姓名:陈敏  杨建民  张豪  王依婷
作者单位:1. 浙江师范大学数学与计算机科学学院, 浙江 金华 321004
基金项目:国家自然科学基金(No.11971437);浙江省自然科学基金(No.LY19A010015)。
摘    要:假设G=(VEF)是一个平面图。如果e1e2G中两条相邻边且在关联的面的边界上连续出现,那么称e1e2面相邻。图G的一个弱完备k-染色是指存在一个从VEFk色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及VEF中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χvefG)。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
本文献已被 维普 等数据库收录!
点击此处可从《运筹学学报》浏览原始摘要信息
点击此处可从《运筹学学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号