On the 4-color theorem for signed graphs

2019/06/13 by František Kardoš, Kardoš, František, Jonathan Narboni +1 · 2 citations
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1906.05638

arxiv created 2019/06/13 · arxiv updated 2019/06/14

Abstract

There are several ways to generalize graph coloring to signed graphs. Máčajová, Raspaud and Škoviera introduced one of them and conjectured that in this setting, for signed planar graphs four colors are always enough, generalising thereby The Four Color Theorem. We disprove the conjecture.

Cited by

• 3-colorable planar graphs have an intersection segment representation using 3 slopes
• Fractional balanced chromatic number and arboricity of planar (signed) graphs

Related

• A note on two conjectures that strengthen the four colour theorem
• A formal proof of the four color theorem
• The Four Color Theorem -- A New Simple Proof by Induction
• A Simple Proof for the Four-Color Theorem
• A Simple Proof of the Four-Color Theorem