New bound on the odd chromatic number of planar graphs with maximum degree at most 4

• Vinícius de Souza Carvalho UFABC
• Carla Negri Lintzmayer UFABC
• Maycon Sambinelli UFABC

DOI: https://doi.org/10.5753/etc.2025.9399

Resumo

An odd coloring of a graph G is a proper vertex coloring where, for every vertex v ∈ V (G), there is a color that appears an odd number of times in N_G(v). The smallest k for which G admits an odd coloring is the (proper) odd chromatic number and it is denoted χ_o(G). This coloring was introduced in 2022, and it was conjectured that χ_o(G) ≤ 5 for every planar graph G, while the best known upper bound is χ_o(G) ≤ 8. It is also known that any graph G satisfies χ_o(G) ≤ ⌊3∆(G)/2⌋+2. This paper shows that every planar graph G with ∆(G) ≤ 4 has χ_o(G) ≤ 7.

Referências

Caro, Y., Petruševski, M., and Škrekovski, R. (2022). Remarks on odd colorings of graphs. Discrete Appl. Math., 321:392–401.

Cho, E.-K., Choi, I., Kwon, H., and Park, B. (2023). Odd coloring of sparse graphs and planar graphs. Discrete Math., 346(5):Paper No. 113305, 7.

Cranston, D. W. and West, D. B. (2017). An introduction to the discharging method via graph coloring. Discrete Math., 340(4):766–793.

Dai, T., Ouyang, Q., and Pirot, F. (2024). New bounds for odd colourings of graphs. Electron. J. Combin., 31(4):Paper No. 4.57, 22.

Kashima, M. and Zhu, X. (2024). Odd 4-coloring of outerplanar graphs. Graphs Combin., 40(6):Paper No. 108, 10.

Miao, Z., Sun, L., Tu, Z., and Yu, X. (2024). On odd colorings of planar graphs. Discrete Math., 347(1):Paper No. 113706, 11.

Petr, J. and Portier, J. (2023). The odd chromatic number of a planar graph is at most 8. Graphs Combin., 39(2):Paper No. 28, 8.

Petruševski, M. and Škrekovski, R. (2022). Colorings with neighborhood parity condition. Discrete Appl. Math., 321:385–391.