Acyclic Coloring of Certain Chemical Structures

Document Type : Research Paper


School of Advanced Sciences, Vellore Institute of Technology, Chennai – 600127, India


A rapidly developing field of science and technology is nanobiotechnology. Nanotube, nanostar and polyomino chain are critical and widespread molecular structures extensively used in the domains of pharmaceuticals, chemical engineering, and medical science. Additionally, these structures serve as the foundational building blocks for other, more intricate chemical molecular structures. In this paper, certain chemical structures like nanostar dendrimer, oxide network, silicate network, boron nanosheet and polyomino chains have been acyclically colored using the concept of vertex cut and matching. Also, we determine the acyclic coloring parameters for the networks under consideration and find a relation between them.


Main Subjects

[1] A. W. Bosman, H. M. Janssen and E. W. Meijer, About dendrimers: structure, physical properties, and applications, Chem. Rev. 99 (7) (1999) 1665–1688,
[2] P. Manuel and I. Rajasingh, Topological properties of silicate networks, 5th IEEE GCC Conference and Exhibition (2009) 1–17,
[3] J. Kunstmann and A. Quandt, Broad boron sheets and boron nanotubes: an ab initio study of structural, electronic, and mechanical properties, Phys. Rev. B. 74 (3) (2006) p. 035413,
[4] P. Manuel, Computational aspects of carbon and boron nanotubes, Molecules. 15 (12) (2010) 8709–8722,
[5] R. K. F. Lee, B. J. Cox and J. M. Hill, Ideal polyhedral model for boron nanotubes with distinct bond lengths, J. Phys. Chem. C. 113 (46) (2009) 19794–19805,
[6] H. Tang and S. Ismail-Beigi, Novel precursors for boron nanotubes: the competition of two-center and three-center bonding in boron sheets, Phys. Rev. Lett. 99 (11) (2007) p. 115501,
[7] X. Yang, Y. Ding and J. Ni, Ab initio prediction of stable boron sheets and boron nanotubes: structure, stability and electronic properties, Phys. Rev. B. 77 (4) (2008) p. 041402,
[8] V. Bezugly, J. Kunstmann, B. Grundkötter-Stock, T. Frauenheim, T. Niehaus, and G. Cuniberti, Highly conductive boron nanotubes: transport properties, work functions, and structural stabilities, ACS Nano. 5 (6) (2011) 4997–5005,
[9] P. John, H. Sachs and H. Zerntiz, Counting perfect matchings in polyominoes with an application to the dimer problem, Appl. Math. 19 (1987) 465–477.
[10] P. W. Kasteleyn, The statistics of dimers on a lattice: I. the number of dimer arrangements on a quadratic lattice, Physica. 27 (12) (1961) 1209–1225.
[11] S. W. Golomb, Checker boards and polyominoes, Am. Math. Mon. 61 (10) (1954) 675–682,
[12] G. Barequet, S. W. Golomb and D. A. Klarner, Polyominoes, in: J. E. Goodman, J. O’Rourke and C. D. Tóth (Eds.), Handbook of discrete and computational geometry, CRC Press LLC, Boca Raton, 1997.
[13] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390–408,
[14] J. Fiamcik, The acyclic chromatic class of a graph, Math. Slovaca. 28 (1978) 139–145.
[15] N. Alon and A. Zaks, Algorithmic aspects of acyclic edge colorings, Algorithmica. 32 (2002)
[16] H. Alt, U. Fuchs and K. Kriegel, On the number of simple cycles in planar graphs, Comb. Probab. Comput. 8(5) (1999) 397–405.
[17] A. V. Kostochka, Upper bounds on the chromatic functions of graphs, Ph.D. Thesis, Novosibirsk, Russian, 1978.
[18] A. H. Gebremedhin, A. Tarafdar, F. Manne and A. Pothen, New acyclic and star coloring algorithms with application to computing hessians, SIAM J. Sci. Comput. 29 (3) (2007) 1042–1072,
[19] D. Amar, A. Raspaud and O. Togni, All-to-all wavelength-routing in all-optical compound networks, Discrete Math. 235 (2001) 353–363,
[20] I. Moffatt, Unsigned state models for the jones polynomial, Ann. Comb. 15 (2011) 127–146,
[21] J. E. Graver and E. J. Hartung, Kekuléan benzenoids, J. Math. Chem. 52 (2014) 977–989,
[22] A. T. Balaban, Applications of graph theory in chemistry, J. Chem. Inf. Comput. Sci. 25 (3) (1985) 334–343,
[23] A. B. Greeni and V. V. Navis, Acyclic coloring of certain graphs, J. Adv. Comput. Intell. Intell. Inform. 27 (1) (2023) 101–104.
[24] J.Wang and L. Miao, Acyclic coloring of graphs with maximum degree at most six, Discrete Math. 342 (2019) 3025–3033,
[25] T. Wang and Y. Zhang, Acyclic edge coloring of graphs, Discret. Appl. Math. 167 (2014) 290–303,
[26] I. Rajasingh, R. Rajan and D. Paul, A new approach to compute acyclic chromatic index of certain chemical structures, Iranian J. Math. Chem. 6 (1) (2015) 51–61,
[27] F. Simonraj and A. George, Topological properties of few poly oxide, poly silicate, DOX and DSL networks, Int. J. Future Comput. Commun. 2 (2) (2013) 90–95,