Acyclic Coloring of Certain Graphs

A. Berin Greeni; V. Vinitha Navis

doi:10.20965/jaciii.2023.p0101

single-jc.php

« previous

JACIII Vol.27 No.1 pp. 101-104

doi: 10.20965/jaciii.2023.p0101

(2023)

Research Paper:

Views over last 60 days: 225

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

Received:

June 30, 2022

Accepted:

September 3, 2022

Published:

January 20, 2023

Keywords:

acyclic chromatic number, generalized fan graph, generalized Möbius ladder graph, flower snark graph

Abstract

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:

References

[1] B. Grünbaum, “Acyclic colorings of planar graphs,” Israel J. of Mathematics, Vol.14, pp. 390-408, 1973.
[2] A. V. Kostochka, “Upper bounds on the chromatic functions of graphs,” Ph.D. Thesis, Novosibirsk, Russia, 1978.
[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] A. T. Balaban, “Applications of graph theory in chemistry,” J. of Chemical Information and Computer Sciences, Vol.25, pp. 334-343, 1985.
[5] J. E. Graver and E. J. Hartung, “Kekuléan benzenoids,” J. of Mathematical Chemistry, Vol.52, pp. 977-989, 2014.
[6] I. Moffatt, “Unsigned state models for the Jones polynomial,” Annals of Combinatorics, Vol.15, Article No.127, 2011.
[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] 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] I. Muhammad, H. Ma, R. N. Abdul, and M. Mobeen, “Generalized Möbius Ladder and its Metric Dimension,” arXiv:1708.05199, 2017.
[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 article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[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.