آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 118 |
| تعداد مقالات | 1,481 |
| تعداد مشاهده مقاله | 1,593,425 |
| تعداد دریافت فایل اصل مقاله | 1,490,441 |
Set colorings of the Cartesian product of some graph families | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 15، دوره 10، شماره 4، اسفند 2025، صفحه 1001-1016 اصل مقاله (1.02 M) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2024.29090.1840 | ||
| نویسندگان | ||
| Mark Anthony C. Tolentino* ؛ Janree Ruark C. Gatpatan؛ Timothy Robin Y. Teng | ||
| Department of Mathematics, Ateneo de Manila University, Quezon City, Philippines | ||
| چکیده | ||
| Neighbor-distinguishing colorings, which are colorings that induce a proper vertex coloring of a graph, have been the focus of different studies in graph theory. One such coloring is the set coloring. For a nontrivial graph $G$, let $c:V(G)\to \mathbb{N}$ and define the neighborhood color set $NC(v)$ of each vertex $v$ as the set containing the colors of all neighbors of $v$. The coloring $c$ is called a set coloring if $NC(u)\neq NC(v)$ for every pair of adjacent vertices $u$ and $v$ of $G$. The minimum number of colors required in a set coloring is called the set chromatic number of $G$ and is denoted by $\chi_s (G)$. In recent years, set colorings have been studied with respect to different graph operations such as join, comb product, middle graph, and total graph. Continuing the theme of these previous works, we aim to investigate set colorings of the Cartesian product of graphs. In this work, we investigate the gap given by $\max\{ \chi_s(G), \chi_s(H) \} - \chi_s(G\ \square\ H)$ for graphs $G$ and $H$. In relation to this objective, we determine the set chromatic numbers of the Cartesian product of some graph families. | ||
| کلیدواژهها | ||
| set coloring؛ Cartesian product؛ neighbor-distinguishing coloring | ||
| مراجع | ||
|
[1] G. Chartrand, F. Okamoto, C.W. Rasmussen, and P. Zhang, The set chromatic number of a graph, Discuss. Math. Graph Theory 29 (2009), no. 3, 545–561.
[2] G. Chartrand, F. Okamoto, E. Salehi, and P. Zhang, The multiset chromatic number of a graph, Math. Bohem. 134 (2009), no. 2, 191–209. http://dx.doi.org/10.21136/MB.2009.140654
[3] G. Chartrand, F. Okamoto, and P. Zhang, Neighbor-distinguishing vertex colorings of graphs, J. Comb. Math. Comb. Comput. 74 (2010), 223–251.
[4] G. Chartrand, F. Okamoto, and P. Zhang, The sigma chromatic number of a graph, Graphs Combin. 26 (2010), no. 6, 755–773. https://doi.org/10.1007/s00373-010-0952-7 [5] A. Dudek, D. Mitsche, and P. Pralat, The set chromatic number of random graphs, Discrete Appl. Math. 215 (2016), 61–70. https://doi.org/10.1016/j.dam.2016.07.011
[6] G.J. Eugenio, M.J.P. Ruiz, and M.A.C. Tolentino, The set chromatic numbers of the middle graph of graphs, J. Phys. Conf. Ser. 1836 (2021), no. 1, Atricle ID: 012014.
[7] B.C. Felipe, A.D. Garciano, and M.A.C. Tolentino, On the set chromatic number of the join and comb product of graphs, J. Phys. Conf. Ser. 1538 (2020), no. 1, Atricle ID: 012009.
[8] R. Gera, F. Okamoto, C. Rasmussen, and P. Zhang, Set colorings in perfect graphs, Math. Bohem. 136 (2011), no. 1, 61–68. http://dx.doi.org/10.21136/MB.2011.141450
[9] F. Harary, Graph Theory, Reading, MA: Addison-Wesley, 1994.
[10] F. Okamoto, C.W. Rasmussen, and P. Zhang, Set vertex colorings and joins of graphs, Czech. Math. J. 59 (2009), no. 4, 929–941. https://doi.org/10.1007/s10587-009-0064-9
[11] G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957), 515–525. https://doi.org/10.4153/CJM-1957-060-7
[12] J.S. Sereni and Z. Yilma, A tight bound on the set chromatic number, Discuss. Math. Graph Theory 33 (2013), no. 2, 461–465. https://doi.org/10.7151/dmgt.1679
[13] M.A.C. Tolentino and G.R.J. Eugenio, The set chromatic numbers of the middle graph of tree families, Int. J. Math. Comput. Sci. 18 (2023), no. 3, 509–519. http://ijmcs.future-in-tech.net
[14] M.A.C. Tolentino, G.R.J. Eugenio, and M.J.P. Ruiz, On the total set chromatic number of graphs, Theory Appl. Graphs 9 (2022), no. 2, Article number 5 https://doi.org/10.20429/tag.2022.090205 | ||
|
آمار تعداد مشاهده مقاله: 639 تعداد دریافت فایل اصل مقاله: 1,331 |
||