Mácajová–Raspaud–Škoviéra signed Four Color conjecture

From papers

All graphs are finite, simple, undirected graphs. Let GG be a graph and let σ:E(G){1,+1}\sigma:E(G)\to\{-1,+1\} be a signature; the pair (G,σ)(G,\sigma) is a signed graph, with underlying graph GG. A kk-signed coloring of (G,σ)(G,\sigma) uses the kk colors specified according to the parity of kk, and assigns colors so that for every edge e=uve=uv, c(u)σ(e)c(v)c(u)\ne\sigma(e)\cdot c(v). Write χ(G)\chi(G) for the least kk admitting such a coloring. Mácajová–Raspaud–Škoviéra's conjecture. If GG is a simple signed planar graph, then

χ(G)4.\chi(G)\le 4.

This is the signed-graph analogue of the Four Color Theorem: it asserts that every simple signed planar graph admits a signed coloring with at most four colors. The source attributes the conjecture to Mácajová, Raspaud and Škoviéra; its resolution is not established by the supplied context.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

František Kardoš and Jonathan Narboni, “On the 4-color theorem for signed graphs”, arXiv:1906.05638 (2019).

Solutions 0

No solutions have been posted yet.