Chromatic Index Of Some Classes Of Graph
Volume 3 - Issue 7, July 2019 Edition
[Download Full Paper]
Author(s)
Renson Aguilar Robles
Keywords
Chromatic Index, Chromatic Index Polynomial
Abstract
Graphs considered in this study are finite simple graphs. Edge coloring properties of fan graph, star graph, bistar graph, helm graph, and friendship graph are investigated and their chromatic indices are determined. The chromatic index determines the minimum number of color used to color the edges of a particular graph. Also, the study aimed to determine the chromatic index polynomial of the graphs stated above. Vizing’s classifications of graph based on its maximum degree are also taken into consideration. This study, as a pure research, is descriptive and expository in nature. This provided comprehensive description of the concepts in mathematics, particularly on the context of graph theory, which may create an abstraction of the concepts of some classes of graphs and the theory of edge coloring. Results of the study showed that almost all graphs stated above are of class 1. Their chromatic indices were determined based on their maximum degree. Furthermore, the chromatic index polynomial of the graphs considered in this study is obtained to determine the number of ways to color the edges of a particular graph by using at most colors
References
[1] F. Harary. Graph Theory. Addison – Wesley Publishing Company Inc., 1994.
[2] T. Beseri Edge Coloring of a Graph, Dissertation Paper, Izmir Institute of Technology, Izmir, Turkey. Retrieved from http://web.iyte.edu.tr/– tinabeseri/Tina-tez.pdf.2004
[3] W. Ruksasakchai and T. Wang. List Strong Edge Coloring of Some Classes of Graphs, Australasian Journal of Combinatorics Vol 68(1): 106–117, 2017
[4] B. Luzar, M. Petrusevski and R. Skrekovski. Odd Edge Coloring of Graphs. ARS mathematica Contemporanea Vol 9: 267–277. 2015 Retrieved from http://amcjournal.eu
[5] N. Ramya, K. Rangarajan and R. Sattanathan. On Rainbow Coloring of Some Classes of Graphs International Journal of Computer Applications Vol. 4666 No. 18. 2012
[6] G. Chartrand and P. Zhang. Chromatic Graph Theory, Chapman and Hall/CRC. 2009
[7] O. Ore. The Four Color Problem. Academic Press, New York. 1967
[8] S. Skiena. Trees. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison – Wesley. 1990
[9] E. Weisstein. Helm Graph. MathWorld – A Wolfram Web, 2012.Retrieved from: http://mathworld.wolfram.com/Helm Graph.html
[10] E. Weisstein. Dutch Windmill Graph, From MathWorld – A Wolfram Web Resource. 2012 Retrieved from:http://mathworld. wolfram.com/Dutch WindmillGraph.html
[11] G. Chartrand and P. Zhang Introduction to Graph Theory. Mc Graw Hill, Reading, Singapore. 2005
[12] V.G. Vizing. On an Estimate of the Chromatic class of a Graph. Russian Diskret Analiz. Vol. 3. 1964
