Equitable Edge Coloring of Strong Product of Cycle, Complete Graphs

S. Manimaran¹ , S. Moidheen Aliyar² , K. Manikandan³

Section:Survey Paper, Product Type: Isroset-Journal
Vol.6 , Issue.1 , pp.303-306, Feb-2019

CrossRef-DOI:   https://doi.org/10.26438/ijsrmss/v6i1.303306

Online published on Feb 28, 2019

Copyright © S. Manimaran, S. Moidheen Aliyar, K. Manikandan . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

446 Views    278 Downloads    90 Downloads

Abstract :
An edge coloring of graph G is equitable if for each vertex v of G, the number of edges of any one color incident with v differs from the number of edges of any other color incident with v by at most one. In this paper, we obtain the exact expressions for the equitable edge coloring of strong product of C_(n ) K_m.

Key-Words / Index Term :
Equitable edge coloring, Product graph, Cycle, Complete graph

References :
[1] Erdős, Paul (1964), "Problem 9", in Fieldler, M., Theory of Graphs and its Applications, Prague: Czech Acad. Sci. Publ., p. 159.
[2] M.A. Gang, M.A. Ming, “The equitable total chromatic number of some join graphs”, open journal of Applied Sciences (2012).
[3] R. P. Gupta, "The Chromatic Index and the Degree of a Graph", Not. Amer. Math. Soc. 13, 719, 1966.
[4] A. Hajnal, and E. Szemer´edi, (1970) “Proof of a conjecture of P. Erd˝os”, In Combinatorial Theory and its Application (P. Erd˝os, A. R´enyi, and V. T. S´os, eds), North-Holland, London, pp. 601–623.
[5] R. Hammack, W. Imrich and S. Klavzar, “Handbook of Product Graphs”, CRC Press, Taylor & Francis Group, Boca Raton, 2011
[6] H. A. Kierstead, A. V. Kostochka, (2008), "A short proof of the Hajnal-Szemerédi theorem on equitable colouring", Combinatorics, Probability and Computing, 17 (2): 265–270.
[7] S. Mohan, J. Geetha, K. somasundaram, “Total coloring of certain classes of product graphs”, Electronic notes in Disc. Math. 53(2016), 173-180.
[8] G. Sabidussi, “Graph Multiplication”, Math. Z. 1960, 72, 446-457.
[9] P. Seymour (1974), "Problem section", in McDonough, T. P.; Mavron, Eds., V. C., Combinatorics: Proceeding of the British Combinatorial Conference 1973, Cambridge, UK: Cambridge Univ. Press, pp. 201–202.
[10] S. Skiena, "Edge Colorings" §5.5.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica.Reading, MA: Addison-Wesley, p. 216, 1990.
[11] V. G. Vizing, “On an Estimate of the Chromatic Class of a p-Graph” [Russian]. Diskret Analiz 3, 23-30, 1964.
[12] V. G. Vizing, “The Cartesian product of graphs” Vyc. Sis. 1963, 9, 30-43.