Choosability in signed planar graphs

DOI10.1016/J.EJC.2015.10.001zbMATH Open1327.05082arXiv1502.04561OpenAlexW1909408525MaRDI QIDQ896077FDOQ896077

Li-Gang Jin, Yingli Kang, Eckhard Steffen

Publication date: 11 December 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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 $kin3,4,5,6$, every signed planar graph without circuits of length $k$ 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.

Full work available at URL: https://arxiv.org/abs/1502.04561

zbMATH Keywords

5-choosability

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Signed graph coloring
• Every planar graph is 5-choosable
• A short list color proof of Grötzsch's theorem
• 3-list-coloring planar graphs of girth 5
• Signed Graphs and Geometry
• List colourings of planar graphs
• Choosability and edge choosability of planar graphs without five cycles
• How colorful the signed graph?
• The 4-choosability of plane graphs without 4-cycles
• Planar graphs without cycles of specific lengths
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (15)

• Hajós-like theorem for signed graphs
• Variable degeneracy on toroidal graphs
• Planar graphs without intersecting 5-cycles are signed-4-choosable
• Edge coloring of the signed generalized Petersen graph
• Concepts of signed graph coloring
• A generalization of Noel-Reed-Wu theorem to signed graphs
• A sufficient condition for DP-4-colorability
• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs
• Path choosability of planar graphs
• Signed colouring and list colouring of k‐chromatic graphs
• Choosability of planar graphs
• Every signed planar graph without cycles of length from 4 to 8 is 3-colorable
• Cover and variable degeneracy
• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• Degree choosable signed graphs

This page was built for publication: Choosability in signed planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896077)