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

At least 6 years old · documented by

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.