پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 41 |
| تعداد شماره‌ها | 1,129 |
| تعداد مقالات | 9,669 |
| تعداد مشاهده مقاله | 17,608,775 |
| تعداد دریافت فایل اصل مقاله | 12,294,286 |
The Smallest Number of Colors Needed for a Coloring of the Square of the Cartesian Product of Certain Graphs | ||
| Control and Optimization in Applied Mathematics | ||
| مقاله 6، دوره 8، شماره 1، شهریور 2023، صفحه 83-93 اصل مقاله (465.81 K) | ||
| نوع مقاله: Research Article | ||
| شناسه دیجیتال (DOI): 10.30473/coam.2022.54855.1194 | ||
| نویسندگان | ||
| Sajad Sohrabi Hesan؛ Freydoon Rahbarnia* ؛ Mostafa Tavakolli | ||
| Department of Applied Mathematics, Ferdowsi University of Mashhad, P.O. Box 1159, Mashhad 91775, Iran. | ||
| چکیده | ||
| 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$. | ||
| کلیدواژه‌ها | ||
| 2-Distance coloring؛ Chromatic number؛ Cartesian product؛ Dragon graph | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 245 تعداد دریافت فایل اصل مقاله: 156 |
||