Acyclic chromatic index of chordless graphs

DOI10.1016/J.DISC.2023.113434MaRDI QIDQ6041561zbMATH OpenFDO

Authors Manu Basavaraju, S. M. Hegde, Shashanka Kulamarva

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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)

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.

Recommendations

• Acyclic edge coloring of chordal graphs with bounded degree
• Edge-colouring and total-colouring chordless graphs
• Strong chromatic index of chordless graphs
• scientific article; zbMATH DE number 90562
• Acyclic chromatic index of planar graphs with triangles

Cites work

• scientific article; zbMATH DE number 3717365 (Why is no real title available?)
• scientific article; zbMATH DE number 3603300 (Why is no real title available?)
• scientific article; zbMATH DE number 3616457 (Why is no real title available?)
• A Linear Algorithm for Edge-Coloring Series–Parallel Multigraphs
• Acyclic and oriented chromatic numbers of graphs
• Acyclic chromatic indices of \(K_4\)-minor free graphs
• Acyclic colorings of planar graphs
• Acyclic edge chromatic number of outerplanar graphs
• Acyclic edge coloring of 2-degenerate graphs
• Acyclic edge coloring through the Lovász local lemma
• Acyclic edge colorings of graphs
• Acyclic edge-coloring of planar graphs
• Acyclic edge-coloring of planar graphs: \(\Delta\) colors suffice when \(\Delta\) is large
• Algorithmic aspects of acyclic edge colorings
• All-to-all wavelength-routing in all-optical compound networks
• Edge-colouring and total-colouring chordless graphs
• Erratum to “Acyclic Edge Chromatic Number of Outerplanar Graphs”
• Graph theory
• Minimally 2-connected graphs.
• NP completeness of finding the chromatic index of regular graphs
• On Minimal Blocks
• On graphs with no induced subdivision of \(K_4\)
• Optimal acyclic edge-coloring of cubic graphs
• Star coloring of graphs
• The NP-Completeness of Edge-Coloring

Cited in

(5)

• scientific article; zbMATH DE number 5631826 (Why is no real title available?)
• scientific article; zbMATH DE number 4214033 (Why is no real title available?)
• Acyclic chromatic index of triangle-free 1-planar graphs
• d‐Regular graphs of acyclic chromatic index at least d+2
• Chromatic index of simple hypergraphs

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)