The Acyclic Chromatic Index is Less than the Double of the Max Degree

arXiv1901.07856MaRDI QIDQ6312912FDOQ6312912

Authors: L. M. Kirousis, John Livieratos 

Publication date: 23 January 2019

Abstract: The acyclic chromatic index of a graph $G$ is the least number of colors needed to properly color its edges so that none of its cycles is bichromatic. In this work, we show that $2Delta-1$ colors are sufficient to produce such a coloring, where $Delta$ is the maximum degree of the graph. In contrast with most extant randomized algorithmic approaches to the chromatic index, where the algorithms presuppose enough colors to guarantee properness deterministically and use randomness only to deal with the bichromatic cycles, our randomized, Moser-type algorithm produces a not necessarily proper random coloring, in a structured way, trying to avoid cycles whose edges of the same parity are homochromatic, and only when this goal is reached it checks for properness. It repeats until properness is attained.

Mathematics Subject Classification ID

Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: The Acyclic Chromatic Index is Less than the Double of the Max Degree

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