Article ID Journal Published Year Pages File Type
4653356 European Journal of Combinatorics 2016 10 Pages PDF
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
, , ,