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   

  1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China
  • Online:2018-08-15 Published:2018-08-09


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

  1. 西安电子科技大学 数学与统计学院,西安 710071

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”的关于符号平面图的对应结论。

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