| 不含特殊子式的符号图的选择数 |
| |
| 引用本文： | 宫 辰,武丽芳,刘维婵,张 欣. 不含特殊子式的符号图的选择数[J]. 计算机工程与应用, 2018, 54(16): 55-58. DOI: 10.3778/j.issn.1002-8331.1706-0284 |
| |
| 作者姓名： | 宫 辰 武丽芳 刘维婵 张 欣 |
| |
| 作者单位： | 西安电子科技大学 数学与统计学院，西安 710071 |
| |
| 摘 要： | 针对符号图的列表点染色问题，证明了任何不含[K5]-子式或[K3,3]-子式的符号图的选择数至多为5，并且此处的上界5是不可再降低的，从而推广了Jin、Kang与Steffen发表于“European Journal of Combinatorics，2016，52：234-243”的关于符号平面图的对应结论。
|
| 关 键 词： | 图论 符号图 列表点染色 选择数 子式 |
Choosability of signed graphs without certain minors |
| |
| 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. DOI: 10.3778/j.issn.1002-8331.1706-0284 |
| |
| Authors: | GONG Chen WU Lifang LIU Weichan ZHANG Xin |
| |
| Affiliation: | School of Mathematics and Statistics, Xidian University, Xi’an 710071, China |
| |
| 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”. |
| |
| Keywords: | graph theory signed graph list vertex coloring choosability minor |
|
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
|
