Choosability in signed planar graphs

DOI10.1016/J.EJC.2015.10.001MaRDI QIDQ896077zbMATHOpenAlexFDO

Authors Eckhard Steffen, Li-Gang Jin, Yingli Kang

Publication date 11 December 2015

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

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)

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.

Recommendations

• Planar graphs without intersecting 5-cycles are signed-4-choosable
• A refinement of choosability of graphs
• Every plane graph with girth at least 4 without 8- and 9-circuits is 3-choosable
• Every signed planar graph without cycles of length from 4 to 8 is 3-colorable
• Choosability and edge choosability of planar graphs without five cycles

Cites work

• scientific article; zbMATH DE number 986968 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• 3-list-coloring planar graphs of girth 5
• A short list color proof of Grötzsch's theorem
• Choosability and edge choosability of planar graphs without five cycles
• Every planar graph is 5-choosable
• How colorful the signed graph?
• List colourings of planar graphs
• Planar graphs without cycles of specific lengths
• Signed Graphs and Geometry
• Signed graph coloring
• The 4-choosability of plane graphs without 4-cycles

Cited in

(18)

• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs
• A refinement of choosability of graphs
• Concepts of signed graph coloring
• Edge coloring of the signed generalized Petersen graph
• Hajós-like theorem for signed graphs
• Path choosability of planar graphs
• Every signed planar graph without cycles of length from 4 to 8 is 3-colorable
• Separating signatures in signed planar graphs
• Variable degeneracy on toroidal graphs
• A sufficient condition for DP-4-colorability
• \(4\)-colouring of generalized signed planar graphs
• A generalization of Noel-Reed-Wu theorem to signed graphs
• Planar graphs without intersecting 5-cycles are signed-4-choosable
• Choosability of planar graphs
• Cover and variable degeneracy
• Signed colouring and list colouring of k‐chromatic graphs
• 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)