Petruševski–Škrekovski conjecture on odd colorings of planar graphs
Let be a planar graph. An odd coloring of is a proper vertex coloring such that every non-isolated vertex has a color appearing an odd number of times in its neighborhood; let be the minimum number of colors in such a coloring. Petruševski–Škrekovski conjecture. For every planar graph ,
Petruševski and Škrekovski introduced odd coloring and proved that every planar graph is odd 9-colorable. The conjectured bound 5 remains open.
References
Primary source
Yair Caro, Mirko Petruševski, Riste Škrekovski and Zsolt Tuza, “On strong odd colorings of graphs”, arXiv:2410.02336 (2024).
Additional references
8 papers in this index state this conjecture (2022–2024). The statement above is taken from the most recent of them; the others are arXiv:2407.19362, arXiv:2406.10192, arXiv:2212.06563, arXiv:2205.09317, arXiv:2202.02586, arXiv:2202.11267, arXiv:2201.12381.
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.