List Coloring Under Some Graph Operations

Download PDF


DOI: 10.46793/KgJMat2203.417D


The list coloring of a graph G = G(V,E) is to color each vertex v V (G) from its color set L(v). If any two adjacent vertices have different colors, then G is properly colored. The aim of this paper is to study the list coloring of some graph operations.


Coloring, list coloring, graph operation.


[1]   M. Arezoomand and B. Taeri, Applications of generalized hierarchical product of graphs in computing the Szeged index of chemical graphs, MATCH Commun. Math. Comput. Chem. 64 (2010), 591–602.

[2]   M. Axenovich, A note on graph coloring extensions and list-colorings, Electron. J. Combin. 10 (2003), #N1.

[3]   L. Barrière, F. Comellas, C. Dalfó and M. A. Fiol, The hierarchical product of graphs, Discrete Appl. Math. 157 (2009), 36–48.

[4]   L. Barrière, C. Dalfó, M. A. Fiol and M. Mitjana, The generalized hierarchical product of graphs, Discrete Math. 309 (2009), 3871–3881.

[5]   K. P. Chithra, K. A. Germina and N. K. Sudev, On the sparing number of the edge corona of graphs, International Journal of Computer Applications 118 (1) (2015), 1–5.

[6]   D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs - Theory and Application, Academic Press, New York, 1980.

[7]   P. Erd˝o  s, A. L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1980), 122–157.

[8]   Y. Hou and W. - C. Shiu, The spectrum of the edge corona of two graphs, Electron. J. Linear Algebra 20 (2010), 586–594.

[9]   G. Isaak, Sum list coloring 2 × n arrays, Electron. J. Combin. 9(8) (2002), #N8.

[10]   M. A. Lastrina, List-coloring and sum-list-coloring problems on graphs, Ph. D. Thesis, Lowa State University, 2012.

[11]   E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175–177.

[12]   T. Rackham, A note on KΔ+1-free precolouring with Δ colours, Electron. J. Combin. 16 (2009), #N28.

[13]   M. Tavakoli, F. Rahbarnia and A. R. Ashrafi, Further results on hierarchical product of graphs, Discrete Appl. Math. 161 (2013), 1162–1167.

[14]   Zs. Tuza, Graph colorings with local constraints - a survey, Discuss. Math. Graph Theory 17 (1997), 161–228.

[15]   V. G. Vizing, Colouring the vertices of a graph in prescribed colours (in Russian), Diskret. Anal. 29 (1976), 3–10.

[16]   D. B. West. Introduction to Graph Theory, Prentice Hall Inc., Upper Saddle River, New Jersey, 1996.

[17]   W. Yan, B. -Y. Yang and Y. -N. Yeh, The behavior of Wiener indices and polynomials of graphs under five graph decorations, Appl. Math. Lett. 20 (2007), 290–295.

[18]   Z. Yarahmadi and A. R. Ashrafi, The Szeged, vertex PI, first and second Zagreb indices of corona product of graphs, Filomat 26(3) (2012), 467–472.

[19]   Y. -N. Yeh and I. Gutman, On the sum of all distances in composite graphs, Discrete Math. 135 (1994), 359–365.