Petruševski–Škrekovski conjecture on odd colorings of planar graphs

About 4 years old · traced to

Let GG be a planar graph. An odd coloring of GG is a proper vertex coloring such that every non-isolated vertex has a color appearing an odd number of times in its neighborhood; let χo(G)\chi_o(G) be the minimum number of colors in such a coloring. Petruševski–Škrekovski conjecture. For every planar graph GG,

χo(G)≤5.\chi_o(G)\leq 5.

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

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.