Acyclic chromatic index of fully subdivided graphs and Halin graphs

Abstract : An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph G is called fully subdivided if it is obtained from another graph H by replacing every edge by a path of length at least two. Fully subdivided graphs are known to be acyclically edge colorable using Δ+1 colors since they are properly contained in 2-degenerate graphs which are acyclically edge colorable using Δ+1 colors. Muthu, Narayanan and Subramanian gave a simple direct proof of this fact for the fully subdivided graphs. Fiamcik has shown that if we subdivide every edge in a cubic graph with at most two exceptions to get a graph G, then a'(G)=3. In this paper we generalise the bound to Δ for all fully subdivided graphs improving the result of Muthu et al. In particular, we prove that if G is a fully subdivided graph and Δ(G) ≥3, then a'(G)=Δ(G). Consider a graph G=(V,E), with E=E(T) ∪E(C) where T is a rooted tree on the vertex set V and C is a simple cycle on the leaves of T. Such a graph G is called a Halin graph if G has a planar embedding and T has no vertices of degree 2. Let Kn denote a complete graph on n vertices. Let G be a Halin graph with maximum degree Δ. We prove that, a'(G) = 5 if G is K4, 4 if Δ = 3 and G is not K4, and Δ otherwise.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.165--172
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990595
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:27:52
Dernière modification le : jeudi 7 septembre 2017 - 01:03:37
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:38:17

Fichier

2062-7497-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990595, version 1

Collections

Citation

Manu Basavaraju. Acyclic chromatic index of fully subdivided graphs and Halin graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.165--172. 〈hal-00990595〉

Partager

Métriques

Consultations de la notice

221

Téléchargements de fichiers

229