Ulagammal Subramanian, Vernold Vivin Joseph

DOI Number
First page
Last page


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 χs (G) of G is the least number of colors needed to star color G. Let G = (V,E) be a graph with V = S1 [ S2 [ S3 [ . . . [ St [ T where each Si is a set of all vertices of the same degree with at least two elements and T =V (G) − St i=1 Si. The degree splitting graph DS (G) is obtained by adding vertices w1,w2, . . .wt and joining wi to each vertex of Si for 1 i t. The comb product between two graphs G and H, denoted by G ⊲ H, is a graph obtained by taking one copy of G and |V (G)| copies of H and grafting the ith copy of H at the vertex o to the ith vertex of G. In this paper, we give the exact value of star chromatic number of degree splitting of comb product of complete graph with complete graph, complete graph with path, complete graph with cycle, complete graph with star graph, cycle with complete graph, path with complete graph and cycle with path graph.


Star Coloring; Degree Splitting graph; Comb Product

Full Text:



M. O. Albertson, G. G. Chappell, H. A. Kiestead, A. Kündgen and R. Ramamurthi: Coloring with no 2-colored P 4 ’s. Electron. J. Comb. 11 (2004), Paper # R26.

R. Alfarisi and D. Darmaji: On the star parition dimension of comb product of cycle and complete graph. In: International Conference on Mathematics: Education,

Theory and Application, IOP series Journal of physics: Conference series, 855 2017, 012005.

L. Barriére, F. Comellas, C. Dafió and M. A. Fiol: The hierarchical product of graphs. Discrete Appl. Math. 157 (2009), 39–48.

J. A. Bondy and U. S. R. Murty: Graph theory with applications. MacMillan, London, 1976.

J. Clark and D. A. Holton: A first look at graph theory. World Scinetific, 1969.

T. F. Coleman and J. Moré: Estimation of sparse Hessian matrices and graph

coloring problems. Math. Program. 28(3) (1984), 243–270.

D. Darmaji and R. Alfarisi: On the parition dimension of comb product of path and complete graph. In: International Conference on Mathematics: Pure, Applied

and Computation, AIP Conf.Proc.1867, 020038-1-020038-7.

G. Fertin, A. Raspaud and B. Reed: On Star coloring of graphs. J. Graph theory. 47(3) (2004), 163–182.

B. Grünbaum: Acyclic colorings of planar graphs. Israel J. Math. 14 (1973), 390–408.

F. Harary: Graph theory. Narosa Publishing home, New Delhi 1969.

R. Ponraj and S. Somasundaram: On the degree splitting graph of a graph. Natl. Acad. Sci. Lett. 27 (7-8) (2004), 275–278.

E. Sampathkumar and H. B. Walikar: On splitting graph of a graph. Journal of Karnatak University Science, 25 & 26 (Combined) (1980-81), 13–16.

S. W. Saputro, N. Mardiana and I. A. Purwasih: The metric dimension of

comb product graphs. In: Graph theory conference in honor of Egawa’s 60th birthday, 2013, pp. 10–14.

M. Tavakoli, F. Rahbarnia and A. R. Ashrafi: Distribution of some graph invariants over hierarchical product of graphs. Appl. Math. Comput. 220 (2013), 405–413.

DOI: https://doi.org/10.22190/FUMI2002507S


  • There are currently no refbacks.

© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)