An odd $ c $-coloring of a graph is a proper $ c $-coloring such that each non-isolated vertex has at least one color appearing an odd number of times in its neighborhood. The minimum number of colors in any odd coloring of $ G $, denoted $ \chi_o(G) $, is called the odd chromatic number. This concept was introduced by Petruševski and Škrekovski, who conjectured that every planar graph $ G $ is odd 5-colorable and observed that $ \chi_o(G \square H) \leq \chi_o(G) \cdot \chi_o(H) $ for connected nontrivial graphs $ G $ and $ H $. In this paper, for specific Cartesian product graphs $ G \square H $, such as $ P_m \square P_n $, $ C_m \square P_n $, and $ C_m \square C_n $, we determine the exact value of $ \chi_o(G \square H) $, which establishes tighter upper bounds than the multiplicative bound $ \chi_o(G) \cdot \chi_o(H) $. We show that $ \chi_o(P_m \square P_n) \leq 4 $ with a complete characterization of all cases; $ \chi_o(C_m \square P_n) \leq 5 $ with a full classification for even and odd $ m $; and $ \chi_o(C_m \square C_n) \leq 5 $ with necessary and sufficient conditions for 3-, 4-, and 5-colorability under parity and divisibility constraints. These results significantly improve upon the multiplicative upper bound and provide new constructive methods and theoretical insights for studying odd colorings in Cartesian product graphs. Additionally, we determine that $ \chi_o(K_m\square P_n) = \chi_o(K_m \square C_n) = m $ for $ m = 3 $ and $ C_n $ is an even cycle or $ m \geq 4 $.
Citation: Baojie Liu, Qihang Dou, Fan Yang. The odd coloring of some Cartesian product graphs[J]. AIMS Mathematics, 2026, 11(1): 1311-1331. doi: 10.3934/math.2026056
An odd $ c $-coloring of a graph is a proper $ c $-coloring such that each non-isolated vertex has at least one color appearing an odd number of times in its neighborhood. The minimum number of colors in any odd coloring of $ G $, denoted $ \chi_o(G) $, is called the odd chromatic number. This concept was introduced by Petruševski and Škrekovski, who conjectured that every planar graph $ G $ is odd 5-colorable and observed that $ \chi_o(G \square H) \leq \chi_o(G) \cdot \chi_o(H) $ for connected nontrivial graphs $ G $ and $ H $. In this paper, for specific Cartesian product graphs $ G \square H $, such as $ P_m \square P_n $, $ C_m \square P_n $, and $ C_m \square C_n $, we determine the exact value of $ \chi_o(G \square H) $, which establishes tighter upper bounds than the multiplicative bound $ \chi_o(G) \cdot \chi_o(H) $. We show that $ \chi_o(P_m \square P_n) \leq 4 $ with a complete characterization of all cases; $ \chi_o(C_m \square P_n) \leq 5 $ with a full classification for even and odd $ m $; and $ \chi_o(C_m \square C_n) \leq 5 $ with necessary and sufficient conditions for 3-, 4-, and 5-colorability under parity and divisibility constraints. These results significantly improve upon the multiplicative upper bound and provide new constructive methods and theoretical insights for studying odd colorings in Cartesian product graphs. Additionally, we determine that $ \chi_o(K_m\square P_n) = \chi_o(K_m \square C_n) = m $ for $ m = 3 $ and $ C_n $ is an even cycle or $ m \geq 4 $.
| [1] | A. Bondy, U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, Vol. 244, Springer, 2008. |
| [2] |
Y. Caro, M. Petruševski, R. Škrekovski, Remarks on odd colorings of graphs, Discrete Appl. Math., 321 (2022), 392–401. https://doi.org/10.1016/j.dam.2022.07.024 doi: 10.1016/j.dam.2022.07.024
|
| [3] |
E. K. Cho, I. Choi, H. Kwon, B. Park, Odd coloring of sparse graphs and planar graphs, Discrete Math., 346 (2023), 113305. https://doi.org/10.1016/j.disc.2022.113305 doi: 10.1016/j.disc.2022.113305
|
| [4] |
D. W. Cranston, M. Lafferty, Z. X. Song, A note on odd colorings of 1-planar graphs, Discrete Appl. Math., 330 (2023), 112–117. https://doi.org/10.1016/j.dam.2023.01.011 doi: 10.1016/j.dam.2023.01.011
|
| [5] | V. Dujmović, P. Morin, S. Odak, Odd colourings of graph products, arXiv, 2022. https://doi.org/10.48550/arXiv.2202.12882 |
| [6] | R. Hickingbotham, Odd colourings, conflict-free colourings and strong colouring numbers, arXiv, 2022. https://doi.org/10.48550/arXiv.2203.10402 |
| [7] |
M. Kashima, X. Zhu, Odd 4-coloring of outerplanar graphs, Graphs Combinator., 40 (2024), 108. https://doi.org/10.1007/s00373-024-02842-0 doi: 10.1007/s00373-024-02842-0
|
| [8] |
R. Liu, W. Wang, G. Yu, 1-planar graphs are odd 13-colorable, Discrete Math., 346 (2023), 113423. https://doi.org/10.1016/j.disc.2023.113423 doi: 10.1016/j.disc.2023.113423
|
| [9] | H. Metrebian, Odd colouring on the torus, arXiv, 2022. https://doi.org/10.48550/arXiv.2205.04398 |
| [10] | B. Niu, X. Zhang, An improvement of the bound on the odd chromatic number of 1-planar graphs, In: Q. Ni, W. Wu, Algorithmic aspects in information and management, Lecture Notes in Computer Science, Springer, 13512 (2022), 388–393. https://doi.org/10.1007/978-3-031-16081-3_33 |
| [11] |
M. Petruševski, R. Škrekovski, Colorings with neighborhood parity condition, Discrete Appl. Math., 321 (2022), 385–391. https://doi.org/10.1016/j.dam.2022.07.018 doi: 10.1016/j.dam.2022.07.018
|
| [12] |
J. Petr, J. Portier, The odd chromatic number of a planar graph is at most 8, Graphs Combinator., 39 (2023), 28. https://doi.org/10.1007/s00373-023-02617-z doi: 10.1007/s00373-023-02617-z
|
| [13] |
T. Wang, X. Yang, On odd colorings of sparse graphs, Discrete Appl. Math., 345 (2024), 156–169. https://doi.org/10.1016/j.dam.2023.11.039 doi: 10.1016/j.dam.2023.11.039
|
Figures(15) / Tables(1)
Baojie Liu, Qihang Dou, Fan Yang. The odd coloring of some Cartesian product graphs[J]. AIMS Mathematics, 2026, 11(1): 1311-1331. doi: 10.3934/math.2026056
DownLoad: