Mácajová–Raspaud–Škoviéra signed Four Color conjecture
All graphs are finite, simple, undirected graphs. Let be a graph and let be a signature; the pair is a signed graph, with underlying graph . A -signed coloring of uses the colors specified according to the parity of , and assigns colors so that for every edge , . Write for the least admitting such a coloring. Mácajová–Raspaud–Škoviéra's conjecture. If is a simple signed planar graph, then
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
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.