Local Connective Chromatic Number of Direct Product of Paths and Cycles


  • Canan Ciftci
  • Pinar Dundar


Graph coloring is one of the most important concept in graph
theory. There are many types of coloring. We study on the local connective chromatic number of a graph G that is dened by us. In this paper, we determine the local connective chromatic number of the direct product of two paths Pm Pn, two cycles Cm Cn and for the direct product of a cycle and a path Cm Pn, where m and n are the number of vertices.


[1] N. Alon, E. Lubetzky. Independent sets in tensor graph powers. J. Graph Theory, 54(1)(2007), 73-87.

[2] Dr.P. Bhaskarudu. Some results on kronecker product of two graphs. International Journal of Mathematics Trends and Technology, 1(2012), 34-37.

[3] A. Bottreau and Y. Metivier. Some remarks on the kronecker product of graphs. Information Processing Letters, 68(1998), 55-61.

[4] B. Bresar, W. Imrich, S. Klavzar and B. Zmazek. Hypercubes as direct products. SIAM J. Discrete Math., 18(4)(2005), 778-786.

[5] B. Bresar, S. Klavzar, and D.F. Rall. On the packing chromatic number of Cartesian products, hexagonal lattice, and trees. Discrete Appl. Math., 155(2007), 2303-2311.

[6] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, Fifth edition. Taylor & Francis, 2005.

[7] C. Ciftci and P. Dundar. Some Bounds on Local Connective Chromatic Number. submitted, 2016.

[8] M. Farzan and D.S.Waller. Kronecker products and local joins of graphs. Canad. J. Math., 29(2)(1977), 255-269.

[9] W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris and D. F. Rall. Broadcast chromatic numbers of graphs. Ars Combinatoria, 86(2008), 33-50.

[10] P.K. Jha. Hamiltonian decompositions of products of cycles. Indian J. Pure Appl. Math., 23(10)(1992), 723-729.

[11] S. Klavzar. Coloring graph products - A survey. Discrete Math., 155(1996), 135-145.

[12] M. Klesc and S. Schrtter. On the packing chromatic number of semiregular polyhedra. Acta Electrotechnica et Informatica, 12(2012), 27-31.

[13] C.N. Lai. Optimal construction of all shortest node-disjoint paths in hypercubes with applications. IEEE Transactions on Parallel and Distributed Systems, 23(2012), 1129-1134.

[14] K. Menger. Zur allgemeinen Kurventheorie. Fundementa Mathematicae, 10(1927), 96-115.

[15] D. J. Miller. The categorical product of graphs. Canad. J. Math., 20 (6)(1968), 1511-1521.

[16] L. Volkmann. On local connectivity of graphs. Applied Mathematics Letters, 21(2008), 63-66.

[17] P.M. Weichsel. The kronecker product of graphs. Proceedings of the American Mathematical Society, 13(1)(1962), 47-52.

[18] A. William and S. Roy. Packing chromatic number of cycle related graphs. International Journal of Mathematics and Soft Computing, 4(2014), 27-33.