JACIII Vol.27 No.1 pp. 101-104
doi: 10.20965/jaciii.2023.p0101

Research Paper:

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

June 30, 2022
September 3, 2022
January 20, 2023
acyclic chromatic number, generalized fan graph, generalized Möbius ladder graph, flower snark graph

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.

Cite this article as:
A. Greeni and V. Navis, “Acyclic Coloring of Certain Graphs,” J. Adv. Comput. Intell. Intell. Inform., Vol.27, No.1, pp. 101-104, 2023.
Data files:
  1. [1] B. Grünbaum, “Acyclic colorings of planar graphs,” Israel J. of Mathematics, Vol.14, pp. 390-408, 1973.
  2. [2] A. V. Kostochka, “Upper bounds on the chromatic functions of graphs,” Ph.D. Thesis, Novosibirsk, Russia, 1978.
  3. [3] 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.
  4. [4] A. T. Balaban, “Applications of graph theory in chemistry,” J. of Chemical Information and Computer Sciences, Vol.25, pp. 334-343, 1985.
  5. [5] J. E. Graver and E. J. Hartung, “Kekuléan benzenoids,” J. of Mathematical Chemistry, Vol.52, pp. 977-989, 2014.
  6. [6] I. Moffatt, “Unsigned state models for the Jones polynomial,” Annals of Combinatorics, Vol.15, Article No.127, 2011.
  7. [7] 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.
  8. [8] A. C. Rojas and K. Diaz, “Distance Labellings of Möbius Ladders: A Major Qualifying Project Report,” B.S. Thesis, Worcester Polytechnic Institute, 2013.
  9. [9] I. Muhammad, H. Ma, R. N. Abdul, and M. Mobeen, “Generalized Möbius Ladder and its Metric Dimension,” arXiv:1708.05199, 2017.
  10. [10] 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 site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Feb. 08, 2023