Department of
Applied
Mathematics

On the 4-color theorem for signed graphs

Jonathan Narboni

University of Bordeaux

Abstract

There are several ways to generalize graph coloring to signed graphs. Macajova, Raspaud and Skoviera 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.

Here is the link to the preprint on arViv: https://arxiv.org/abs/1906.05638

Joint work with Frantisek Kardos.