Choosability of signed graphs without certain minors

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

Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (16): 55-58.DOI: 10.3778/j.issn.1002-8331.1706-0284

Previous Articles Next Articles

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

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

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

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

Abstract

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

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

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

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.

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

[1]	WANG Le, HAN Meng, LI Xiaojuan, ZHANG Ni, CHENG Haodong. Review of Classification Methods for Unbalanced Data Sets [J]. Computer Engineering and Applications, 2021, 57(22): 42-52.
[2]	WEN Tingxin, KONG Xiangbo. Research on Extreme Risk Warning in Financial Market from Imbalance Distribution of Samples [J]. Computer Engineering and Applications, 2020, 56(8): 256-260.
[3]	ZHANG Zhonglin, FENG Yibang, ZHAO Zhongkai. Oversampling Method for Unbalanced Data Sets Based on SVM [J]. Computer Engineering and Applications, 2020, 56(23): 220-228.
[4]	WANG Liang, YE Jimin. Hybrid Algorithm of DBSCAN and Improved SMOTE for Oversampling [J]. Computer Engineering and Applications, 2020, 56(18): 111-118.
[5]	LIU Chao, WU Shen, ZHENG Yichao, HOU Weiyan. Classification of Cancer Based on Deep Forest and DNA Methylation [J]. Computer Engineering and Applications, 2020, 56(13): 189-193.
[6]	ZHANG Jiawei, GUO Linming, YANG Xiaomei. Improved Oversampling and Random Forest Algorithm for Imbalanced Data [J]. Computer Engineering and Applications, 2020, 56(11): 39-45.
[7]	MENG Yun, HU Xin, DAI Liang, YU Lei. Connectivity Improvement Resource Allocation Algorithm in Interference Vehicular Networks [J]. Computer Engineering and Applications, 2019, 55(7): 9-15.
[8]	LIU Shudong, ZHANG Ke. Research on Sampling Strategies in Class-Imbalanced Learning [J]. Computer Engineering and Applications, 2019, 55(21): 1-17.
[9]	LUO Kangyang, WANG Guoqiang. Research on Imbalanced Data Classification Based on L-SMOTE and SVM [J]. Computer Engineering and Applications, 2019, 55(17): 55-62.
[10]	ZHANG Yangfan, ZHANG Haipeng, SUN Jun. Lévy-Based Oversampling Technique for Imbalanced Datasets [J]. Computer Engineering and Applications, 2019, 55(16): 150-156.
[11]	LIU Kang1, ZHANG Xueying1, LI Fenglian1, TIAN Yuchu1，2. Graph partitioning method for social networks based on communication load balancing [J]. Computer Engineering and Applications, 2018, 54(4): 66-71.
[12]	LIU Weichan, ZHANG Xin. Equitable vertex arboricity of outer-1-planar graphs [J]. Computer Engineering and Applications, 2018, 54(10): 51-53.
[13]	JIN Yan1, PENG Xinguang2. Optimization design of minorityclass misclassification cost based on classification performance compromise plan [J]. Computer Engineering and Applications, 2016, 52(16): 51-55.
[14]	CHEN Jizhen, NING Aibing, ZHI Zhibing, HU Linlin, ZHANG Huizhen. Exact algorithm for maximum independent set problem in graph theory [J]. Computer Engineering and Applications, 2016, 52(1): 20-22.
[15]	ZHANG Han1, HE Dongjian2. Image segmentation approach by combining texture information and graph theory [J]. Computer Engineering and Applications, 2014, 50(1): 180-184.

Choosability of signed graphs without certain minors

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics