Mácajová–Raspaud–Škoviéra signed Four Color conjecture
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.
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
Sign in to submit a solution.
No solutions have been posted yet.