不含特殊子式的符号图的选择数

doi:10.3778/j.issn.1002-8331.1706-0284

计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (16): 55-58.DOI: 10.3778/j.issn.1002-8331.1706-0284

不含特殊子式的符号图的选择数

宫辰，武丽芳，刘维婵，张欣

西安电子科技大学数学与统计学院，西安 710071

出版日期:2018-08-15 发布日期:2018-08-09

Choosability of signed graphs without certain minors

GONG Chen, WU Lifang, LIU Weichan, ZHANG Xin

School of Mathematics and Statistics, Xidian University, Xi’an 710071, China

Online:2018-08-15 Published:2018-08-09

摘要/Abstract

摘要： 针对符号图的列表点染色问题，证明了任何不含[K5]-子式或[K3,3]-子式的符号图的选择数至多为5，并且此处的上界5是不可再降低的，从而推广了Jin、Kang与Steffen发表于“European Journal of Combinatorics，2016，52：234-243”的关于符号平面图的对应结论。

关键词: 图论, 符号图, 列表点染色, 选择数, 子式

Abstract: The list coloring problem of the signed graphs is investigated in this paper, which proves that the choosability of every signed graph without [K5]-minor or [K3,3]-minor is at most 5, and this upper bound cannot be lowered anymore. This generalizes a corresponding result of Jin, Kang and Steffen on signed planar graph, which is published in “European Journal of Combinatorics, 2016, 52：234-243”.

Key words: graph theory, signed graph, list vertex coloring, choosability, minor

宫辰，武丽芳，刘维婵，张欣. 不含特殊子式的符号图的选择数[J]. 计算机工程与应用, 2018, 54(16): 55-58.

GONG Chen, WU Lifang, LIU Weichan, ZHANG Xin. Choosability of signed graphs without certain minors[J]. Computer Engineering and Applications, 2018, 54(16): 55-58.

[1]	孟芸，胡欣，代亮，余雷. 干扰车载网络中增强连通性的资源分配算法[J]. 计算机工程与应用, 2019, 55(7): 9-15.
[2]	朱泓臻1，陈平华1，蔡桂兰2. LDA模型在红酒数据关系挖掘中的应用研究[J]. 计算机工程与应用, 2019, 55(4): 148-153.
[3]	刘康1，张雪英1，李凤莲1，田玉楚1，2. 基于通信负载均衡的社交网络图分割方法[J]. 计算机工程与应用, 2018, 54(4): 66-71.
[4]	刘维婵，张欣. 外1-平面图的均匀点荫度[J]. 计算机工程与应用, 2018, 54(10): 51-53.
[5]	陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍. 图论中最大独立集问题的精确算法[J]. 计算机工程与应用, 2016, 52(1): 20-22.
[6]	郑艳1，徐国军2，覃锡忠1，贾振红1. 均衡满意度的并行单色连通分支频谱分配算法[J]. 计算机工程与应用, 2014, 50(18): 197-201.
[7]	卢进军1，龙英艳2，潘宏利1. 基于演化图论的可靠的VANETs路由协议[J]. 计算机工程与应用, 2014, 50(13): 96-102.
[8]	张晗1，何东健2. 一种融合纹理信息与图论的图像分割方法[J]. 计算机工程与应用, 2014, 50(1): 180-184.
[9]	韩中1，2，赵升吨2，张贵成2，3，阮卫平3，李建平3，沈红立3. 流程制造系统辨识的自动结构性建模方法[J]. 计算机工程与应用, 2014, 50(1): 227-231.
[10]	曹敦，陈子琦. 一种新的无线传感器网络节点定位算法[J]. 计算机工程与应用, 2012, 48(8): 116-118.
[11]	陈善超，符红光，王颖. 改进的一种图论分割方法在舌像分割中的应用[J]. 计算机工程与应用, 2012, 48(5): 201-203.
[12]	许金星，吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52.
[13]	应德全¹,应晓敏²,叶继华¹. 一种基于图论的聚类算法NeiMu[J]. 计算机工程与应用, 2009, 45(3): 47-50.
[14]	李珂^1，3，连一峰^1，2，3. 一种面向DDoS攻击的网络安全态势评估方法[J]. 计算机工程与应用, 2009, 45(27): 88-91.
[15]	王凤¹，林杰^1，2. 高校排课问题的图论模型及算法[J]. 计算机工程与应用, 2009, 45(27): 240-242.

不含特殊子式的符号图的选择数

Choosability of signed graphs without certain minors

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics