d‐Regular graphs of acyclic chromatic index at least d+2

DOI10.1002/JGT.20422zbMATH Open1215.05053arXiv0804.4681OpenAlexW2951648952MaRDI QIDQ5190332FDOQ5190332

L. Sunil Chandran, Manu Basavaraju, Manoj Kummini

Publication date: 15 March 2010

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The emph{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^{\prime }(G)$. It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that $a^{\prime }(G)leDelta+2$, where $Delta=Delta(G)$ denotes the maximum degree of the graph. Alon et.al also raised the question whether the complete graphs of even order are the only regular graphs which require $Delta+2$ colors to be acyclically edge colored. In this paper, using a simple counting argument we observe not only that this is not true, but infact all d-regular graphs with $2n$ vertices and $d>n$, requires at least $d+2$ colors. We also show that $a^{\prime }(K_{n,n})gen+2$, when $n$ is odd using a more non-trivial argument(Here $K_{n,n}$ denotes the complete bipartite graph with $n$ vertices on each side). This lower bound for $K_{n,n}$ can be shown to be tight for some families of complete bipartite graphs and for small values of $n$. We also infer that for every $d,n$ such that $dge5$, $nge2d+3$ and $dn$ even, there exist $d$-regular graphs which require at least $d+2$-colors to be acyclically edge colored.

Full work available at URL: https://arxiv.org/abs/0804.4681

Recommendations

• The achromatic indices of the regular complete multipartite graphs
• Acyclic chromatic indices of 2-outerplane graphs
• Acyclic chromatic indices of 2-outerplane graphs
• On the chromatic index of graphs with \(2m+1\) vertices and \(2m^2\) edges.
• The acyclic edge chromatic number of a random d‐regular graph is d + 1
• The chromatic index of strongly regular graphs
• \(k\)-regular graphs with the circular chromatic index close to \(k\)
• scientific article; zbMATH DE number 26318
• The circular chromatic index of \(k\)-regular graphs
• Acyclic chromatic index of chordless graphs

zbMATH Keywords

matchingacyclic edge coloringcomplete bipartite graphsperfect 1-factorizationacyclic edge chromatic index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Acyclic colorings of planar graphs
• Acyclic edge colorings of graphs
• Acyclic coloring of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A family of perfect factorisations of complete bipartite graphs

Cited In (9)

• The acyclic edge chromatic number of a random d‐regular graph is d + 1
• Graphs with large palette index
• Acyclic List Edge Coloring of Graphs
• A note on acyclic edge coloring of complete bipartite graphs
• On acyclic edge-coloring of complete bipartite graphs
• Acyclic edge colorings of graphs
• Acyclic edge coloring of graphs with maximum degree 4
• On acyclic edge-coloring of the complete bipartite graphs \(K_{2p-1, 2p-1}\) for odd prime \(p\)
• Acyclic edge coloring of 2-degenerate graphs

This page was built for publication: d‐Regular graphs of acyclic chromatic index at least d+2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5190332)