Chromatic Number of the Corona Product of Complete Graph and Star Graph
DOI:
https://doi.org/10.24252/msa.v13i2.56235Keywords:
Coloring vertex, Chromatic number, Corona product, Complete graph, Star graphAbstract
In this paper, we determine the chromatic number of the corona product of complete graph $K_n$ and star graph $K_{1,m}$. Determination of the chromatic numbers is done by observing patterns, constructing conjectures, and proving them formally. We found that the chromatic number of the corona product of complete graph $K_n$ and star graph $K_{1,m}$ is $\chi\left(K_n\odot K_{1,m}\right)=\left\{\begin{matrix}3,\ \ n=1,2\\n,\ n=3,4,\ldots,\ k\\\end{matrix}\right.$, and the chromatic number of the corona product of star graph $K_{1,m}$ and complete graph $K_n$ is $\chi\left(K_{1,m}\odot K_n\right)=n+1,\ n=1,2,\ldots,\ k$. Furthermore, using Matlab software, a program is created to visualize the coloring of the vertices based on the formula that has been obtained.
References
J. A. Bondy and U. S. R. Murty, Graph Theory. Springer Publishing Company, Incorporated, 2008.
A. S. Asratian, T. M. Denley, and R. H¨aggkvist, Bipartite Graphs and Their Applications. Cambridge University Press,
1998, vol. 131.
F. Harary and R. Frucht, “On the corona of two graph,” Aequationes Mathematicae, pp. 322–325, 1970.
E. G. Goodaire and M. M. Parmenter, Discrete Mathematics with Graph Theory, 2nd ed. Prentice-Hall, 2002.
S. S. B. Ginting and M. Mulyono, “Bilangan kromatik dari graf hasil operasi korona pada graf bintang dan graf lingkaran,” Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam, vol. 2, no. 2, pp. 263–269, 2023.
S. Mohan, J. Geetha, and K. Somasundaram, “Total coloring of the corona product of two graphs,” Australasian Journal of Combinatorics, vol. 68, no. 1, pp. 15–22, 2017.
P. Galinier, J. P. Hamiez, J. K. Hao, and D. Porumbel, “Recent advances in graph vertex coloring,” in Handbook of
Optimization: From Classical to Modern Approach, 2013, pp. 505–528.
S. Simanjuntak and M. Mulyono, “Bilangan kromatik hasil operasi korona graf lingkaran dan graf kubik,” Karismatika, vol. 7, no. 2, pp. 25–31, 2021.
F. Buckley and M. Lewinter, A Friendly Introduction to Graph Theory. New Jersey: Pearson Education, 2003.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Jurnal MSA ( Matematika dan Statistika serta Aplikasinya)
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
