Set colorings of the Cartesian product of some graph families

Document Type : Original paper

Authors

Ateneo de Manila University

Abstract

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.

Keywords

Main Subjects

References

[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
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 23 April 2024

Files

Share

How to cite

Statistics