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

DOI10.1002/JGT.20422MaRDI QIDQ5190332zbMATH OpenOpenAlexFDO

Authors Manu Basavaraju, L. Sunil Chandran, Manoj Kummini

Publication date 15 March 2010

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3603300 (Why is no real title available?)
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• A family of perfect factorisations of complete bipartite graphs
• Acyclic coloring of graphs
• Acyclic colorings of planar graphs
• Acyclic edge colorings of graphs

Cited in

(9)

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