Share This Article:

A Note on Acyclic Edge Colouring of Star Graph Families

Full-Text HTML XML Download Download as PDF (Size:439KB) PP. 253-257
DOI: 10.4236/ajcm.2015.53022    3,469 Downloads   3,790 Views   Citations

ABSTRACT

A proper edge colouring f of a graph G is called acyclic if there are no bichromatic cycles in the graph. The acyclic edge chromatic number or acyclic chromatic index, denoted by , is the minimum number of colours in an acyclic edge colouring of G. In this paper, we discuss the acyclic edge colouring of middle, central, total and line graphs of prime related star graph families. Also exact values of acyclic chromatic indices of such graphs are derived and some of their structural properties are discussed.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Shanasbabu, P. and Chithra, A. (2015) A Note on Acyclic Edge Colouring of Star Graph Families. American Journal of Computational Mathematics, 5, 253-257. doi: 10.4236/ajcm.2015.53022.

References

[1] Grunbaum, B. (1973) Acyclic Colourings of Planar Graphs. Israel Journal of Mathematics, 14, 390-408.
http://dx.doi.org/10.1007/BF02764716
[2] Harrary, F. (1969) Graph Theory. Narosa Publishing House, New Delhi.
[3] Michalak, D. (1983) On Middle and Total Graphs with Coarseness Number Equal 1. Lecture Notes in Mathematics, 1018, 139-150.
http://dx.doi.org/10.1007/BFb0071624
[4] Thilagavathi, K. and Vernold Vivin, J. and Akbar Ali, M.M. (2009) On Harmonious Colouring of Central Graphs. Advances and Applications in Discrete Mathematics, 2, 17-33.
[5] Alon, N. and Zaks, A. (2002) Algorithmic Aspects of Acyclic Edge Colorings. Algorithmica, 32, 611-614.
http://dx.doi.org/10.1007/s00453-001-0093-8
[6] Alon, N., Sudakov, B. and Zaks, A. (2001) Acyclic Edge-Colorings of Graphs. Journal of Graph Theory, 37, 157-167.
http://dx.doi.org/10.1002/jgt.1010
[7] Nesertril, J. and Wormald, N.C. (2005) The Acyclic Edge Chromatic Number of a Random d-Regular Graph Is d + 1. Journal of Graph Theory, 49, 69-74.
http://dx.doi.org/10.1002/jgt.20064
[8] Alon, N., McDiarmid, C. and Reed, B. (1991) Acyclic Colouring of Graphs. Random Structures & Algorithms, 2, 277-288.
http://dx.doi.org/10.1002/rsa.3240020303

  
comments powered by Disqus

Copyright © 2018 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.