On star coloring of modular product of graphs

Abstract

A star coloring of a graph $G$ is a proper vertex coloring in which every path on four vertices in $G$ is not bicolored. The star chromatic number $\chi_{s}\left(G\right)$ of $G$ is the least number of colors needed to star color $G$. In this paper, we find the exact values of the star chromatic number of modular product of complete graph with complete graph $K_m \diamond K_n$, path with complete graph $P_m \diamond K_n$ and star graph with complete graph $K_{1,m}\diamond K_n$. \par All graphs in this paper are finite, simple, connected and undirected graph and we follow \cite{bm, cla, f} for terminology and notation that are not defined here. We denote the vertex set and the edge set of $G$ by $V(G)$ and $E(G)$, respectively. Branko Gr\"{u}nbaum introduced the concept of star chromatic number in 1973. A star coloring \cite{alberton, fertin, bg} of a graph $G$ is a proper vertex coloring in which every path on four vertices uses at least three distinct colors. The star chromatic number $\chi_{s}\left(G\right)$ of $G$ is the least number of colors needed to star color $G$. \par During the years star coloring of graphs has been studied extensively by several authors, for instance see \cite{alberton, col, fertin}.

Keywords

• Star Coloring
• Modular Product
• Star graph

References

1. Albertson, M.O., Chappell, G.G., Kierstead, H.A., Kündgen, A., Ramamurthi, R., Coloring with no 2-colored P4’s. The Electronic Journal of Combinatorics 11 (2004), R26, doi:10. 37236/1779.
2. Bondy, J.A., Murty, U.S.R. Graph theory with applications, MacMillan, London 1976.
3. Clark, J., Holton, D. A., A …rst look at graph theory, World Scienti…c, 1991, doi:10.1142/1280. [ Coleman, T.F., Moré, J., Estimation of sparse Hessian matrices and graph coloring problems, Mathematical Programming, 28(3) (1984), 243–270, doi:10.1007/BF02612334.
4. Fertin, G., Raspaud, A., Reed, B., On Star coloring of graphs, Journal of Graph theory, 47(3) (2004), 163–182, doi:10.1002/jgt.20029.
5. Grünbaum, B., Acyclic colorings of planar graphs, Israel Journal of Mathematics, 14 (1973), 390–408, doi:10.1007/BF02764716
6. Harary, F., Graph theory, Narosa Publishing Home, New Delhi, 1969.
7. Imrich, W., Klavµzar, S., Product Graphs: Structure and Recognition, Wiley, New York 2000.