Acyclic Chromatic Index of Fully Subdivided Graphs and Halin Graphs
Manu Basavaraju
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.
Full Text: PDF PostScript