Acyclic chromatic index of chordless graphs

DOI10.1016/J.DISC.2023.113434zbMATH Open1526.05044arXiv2302.01638MaRDI QIDQ6041561FDOQ6041561

S. M. Hegde, Shashanka Kulamarva, Manu Basavaraju

Publication date: 31 May 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: An acyclic edge coloring of a graph is a proper edge coloring in which there are no bichromatic cycles. The acyclic chromatic index of a graph $G$ denoted by $a^{\prime }(G)$, is the minimum positive integer $k$ such that $G$ has an acyclic edge coloring with $k$ colors. It has been conjectured by Fiamv{c}'{i}k that $a^{\prime }(G)leDelta+2$ for any graph $G$ with maximum degree $Delta$. Linear arboricity of a graph $G$, denoted by $la(G)$, is the minimum number of linear forests into which the edges of $G$ can be partitioned. A graph is said to be chordless if no cycle in the graph contains a chord. Every $2$-connected chordless graph is a minimally $2$-connected graph. It was shown by Basavaraju and Chandran that if $G$ is $2$-degenerate, then $a^{\prime }(G)leDelta+1$. Since chordless graphs are also $2$-degenerate, we have $a^{\prime }(G)leDelta+1$ for any chordless graph $G$. Machado, de Figueiredo and Trotignon proved that the chromatic index of a chordless graph is $Delta$ when $Deltage3$. They also obtained a polynomial time algorithm to color a chordless graph optimally. We improve this result by proving that the acyclic chromatic index of a chordless graph is $Delta$, except when $Delta=2$ and the graph has a cycle, in which case it is $Delta+1$. We also provide the sketch of a polynomial time algorithm for an optimal acyclic edge coloring of a chordless graph. As a byproduct, we also prove that $la(G)=lceilfracDelta2ceil$, unless $G$ has a cycle with $Delta=2$, in which case $la(G)=lceilfracDelta+12ceil=2$. To obtain the result on acyclic chromatic index, we prove a structural result on chordless graphs which is a refinement of the structure given by Machado, de Figueiredo and Trotignon for this class of graphs. This might be of independent interest.

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

zbMATH Keywords

acyclic edge coloringchordless graphsacyclic chromatic indexlinear arboricityminimally 2-connected graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Cites Work

• On graphs with no induced subdivision of \(K_4\)
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Acyclic colorings of planar graphs
• Acyclic edge colorings of graphs
• Title not available (Why is that?)
• Acyclic and oriented chromatic numbers of graphs
• Star coloring of graphs
• Minimally 2-connected graphs.
• On Minimal Blocks
• Graph Theory
• NP completeness of finding the chromatic index of regular graphs
• Edge-colouring and total-colouring chordless graphs
• Title not available (Why is that?)
• Acyclic edge chromatic number of outerplanar graphs
• Acyclic Edge-Coloring of Planar Graphs
• Acyclic edge coloring of 2-degenerate graphs
• Acyclic Edge-Coloring of Planar Graphs: $\Delta$ Colors Suffice When $\Delta$ is Large
• Acyclic chromatic indices of <italic>K</italic><sub>4</sub>-minor free graphs
• Algorithmic aspects of acyclic edge colorings
• Acyclic edge coloring through the Lovász local lemma
• Optimal acyclic edge‐coloring of cubic graphs
• All-to-all wavelength-routing in all-optical compound networks
• A Linear Algorithm for Edge-Coloring Series–Parallel Multigraphs
• Erratum to “Acyclic Edge Chromatic Number of Outerplanar Graphs”

Cited In (5)

• Acyclic chromatic index of triangle-free 1-planar graphs
• Title not available (Why is that?)
• Chromatic index of simple hypergraphs
• d‐Regular graphs of acyclic chromatic index at least d+2
• Title not available (Why is that?)

This page was built for publication: Acyclic chromatic index of chordless graphs

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