The Smallest Number of Colors Needed for a‎ ‎Coloring of the Square of the Cartesian Product of Certain Graphs

Sohrabi Hesan, Sajad; Rahbarnia, Freydoon; Tavakolli, Mostafa

doi:10.30473/coam.2022.54855.1194

Document Type : Research Article

Authors

‎Department of Applied Mathematics‎, ‎Ferdowsi University of Mashhad, ‎P‎.‎O‎. ‎Box 1159‎, ‎Mashhad 91775‎, ‎Iran‎.

https://doi.org/10.30473/coam.2022.54855.1194

Abstract

Given any graph G‎, ‎its square graph G^2 has the same vertex set as G, ‎with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. ‎‎The Cartesian product of graphs G and H is denoted by G□ H. ‎‎One of the most studied NP-hard problems is the graph coloring problem‎. A method such as Genetic Algorithm (GA) is highly preferred to solve the Graph Coloring problem by researchers for many years‎. ‎In this paper‎, ‎we use the graph product approach to this problem‎. ‎In fact‎, ‎we prove that X((D(m',n')□D(m,n))^2)<= 10 for m,n => 3, ‎where D(m‎, ‎n) is the graph obtained by joining a vertex of the cycle C_m to a vertex of degree one of the paths P_n and X(G) is the chromatic number of the graph $G$.

Keywords

References

[1] Chegini, A.G., Hasanvand, M., Mahmoodian, E.S., Moazam, F. (2016). “The square chromatic number of the torus”, Discrete Mathematics, 339, 447-456.

[2] Chiang, S.H., Yan, J.H. (2008). “On L.d; 1-labeling of Cartesian product of a cycle and a path”, Discrete Applied Mathematics, 156, 2867-2881.

[3] Dvoak, Z., Kral, D., Nejedly, P., krekovski, R. (2008). “Coloring squares of planar graphs with girth six”, European Journal of Combinatorics, 29(4), 838-849.

[4] Hamidi, M., Norouzi, K., Rezaei, A. (2021). “On Grey Graphs and their Applications in Optimization”, Control and Optimization in Applied Mathematics, 6(2), 79-96.

[5] Havet, F., Van Den Heuvel, J., McDiarmid, C.J.H., Reed, B. (2007). “List coloring squares of planar graphs”, in: Proc. 2007 Europ. Conf. on Combin, Graph Theory and Applications, EuroComb’07, in: Electronic Notes in Discrete Mathematics, 29, 515-519.

[6] Jamison, R.E., Matthews, G.L., Villalpando, J. (2006). “Acyclic colorings of products of trees”, Information Processing Letters, 99(1), 7-12.

[7] Lih, K.W., Wang, W. (2006). “Coloring the square of an outer planar graph”, Taiwanese Journal of Mathematics, 10, 1015-1023.

[8] Manjula, T., Rajeswari, R. (2018). “Domiator chromatic number of some graphs”, International Journal of Pure and Applied Mathematics, 119(7), 787-795.

[9] Molloy, M., Salavatipour, M.R. (2005). “A bound on the chromatic number of the square of a planar graph”, Journal of Combinatorial Theory, Series, 94(2), 189-213.

[10] Shao, Z., Vesel, A. (2013). “A note on the chromatic number of the square of the Cartesian product of two cycles”, Discrete Mathematics, 313(9), 999-1001.

[11] Sopena, E., Wu, J. (2010). “Coloring the square of the Cartesian product of two cycles”, Discrete Mathematics, 310, 2327-2333.

[12] Sylvester, J.J. (1884). “Mathematical questions with their solutions”, Educ. Times, 41, 171-178.

[13] Tavakoli, M. (2019). “Global forcing number for maximal matchings under graph operations”, Control and Optimization in Applied Mathematics, 4(1), 53-63.

[14] Van Den Heuvel, J., McGuinness, S. (2002). “Coloring the square of a planar graph”, Probability in the Engineering and Informational Sciences Journal Graph Theory, 42, 110-124.

[15] Wegner, G. (1977). “Graphs with given diameter and a coloring problem”, Technical Report, University of Dortmund.

The Smallest Number of Colors Needed for a‎ ‎Coloring of the Square of the Cartesian Product of Certain Graphs

References

References

Volume 8, Issue 1 Open Access PolicyWinter-Spring 2023June 2023Pages 83-93

Volume 8, Issue 1
Open Access Policy
Winter-Spring 2023
June 2023
Pages 83-93