Acyclic Coloring of Certain Graphs
A. Berin Greeni and V. Vinitha Navis
School of Advanced Sciences, Vellore Institute of Technology
Vandalur, Kelambakkam Road, Chennai 600127, India
A graph G with acyclic coloring has no two adjacent vertices with the same color and no bichromatic cycle. Also, the coloring results in a forest when any two-color classes are combined. The concept of acyclic coloring plays a pivotal role in the computation of Hessians, Kekule structures classification, coding theory, and statistical mechanics. In this paper, the acyclic chromatic number of generalized fan graph, generalized Möbius ladder graph and flower snark graph have been determined.
-  B. Grünbaum, “Acyclic colorings of planar graphs,” Israel J. of Mathematics, Vol.14, pp. 390-408, 1973.
-  A. V. Kostochka, “Upper bounds on the chromatic functions of graphs,” Ph.D. Thesis, Novosibirsk, Russia, 1978.
-  A. H. Gebremedhin, A. Tarafdar, F. Manne, and A. Pothen, “New Acyclic and Star Coloring Algorithms with Application to Computing Hessians,” SIAM J. on Scientific Computing, Vol.29, No.3, pp. 1042-1072, 2007.
-  A. T. Balaban, “Applications of graph theory in chemistry,” J. of Chemical Information and Computer Sciences, Vol.25, pp. 334-343, 1985.
-  J. E. Graver and E. J. Hartung, “Kekuléan benzenoids,” J. of Mathematical Chemistry, Vol.52, pp. 977-989, 2014.
-  I. Moffatt, “Unsigned state models for the Jones polynomial,” Annals of Combinatorics, Vol.15, Article No.127, 2011.
-  S. Intaja and T. Sitthiwarttham, “Some graph parameters of fan graph,” Int. J. of Pure and Applied Mathematics, Vol.80, No.2, pp. 217-223, 2012.
-  A. C. Rojas and K. Diaz, “Distance Labellings of Möbius Ladders: A Major Qualifying Project Report,” B.S. Thesis, Worcester Polytechnic Institute, 2013.
-  I. Muhammad, H. Ma, R. N. Abdul, and M. Mobeen, “Generalized Möbius Ladder and its Metric Dimension,” arXiv:1708.05199, 2017.
-  R. Isaacs, “Infinite families of nontrivial trivalent graphs which are not Tait colorable,” The American Mathematical Monthly, Vol.82, No.3, pp. 221-239, 1975.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.