Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653356 | European Journal of Combinatorics | 2016 | 10 Pages |
Abstract
This paper studies the choosability of signed planar graphs. We prove that every signed planar graph is 5-choosable and that there is a signed planar graph which is not 4-choosable while the unsigned graph is 4-choosable. For each k∈{3,4,5,6}k∈{3,4,5,6}, every signed planar graph without circuits of length kk is 4-choosable. Furthermore, every signed planar graph without circuits of length 3 and of length 4 is 3-choosable. We construct a signed planar graph with girth 4 which is not 3-choosable but the unsigned graph is 3-choosable.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ligang Jin, Yingli Kang, Eckhard Steffen,