Acyclic Edge Coloring of 3-sparse Graphs

Nevil Anto, Manu Basavaraju, Shashanka Kulamarva · 2025

Read Acyclic Edge Coloring of 3-sparse Graphs by Nevil Anto, Manu Basavaraju, Shashanka Kulamarva (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11281.txt.

Description

Nevil Anto, Manu Basavaraju, and Shashanka Kulamarva proved a coloring bound in a 2025 graph theory paper. An acyclic edge coloring paints a graph's edges so that no cycle uses just two colors. The least colors needed is the graph's acyclic chromatic index, and a long-standing guess caps it at the max degree plus two.

The team prove the guess for 3-sparse graphs, where each edge touches a low-degree point. Where a light pair of points exists, they prove a stronger cap of degree plus one. The sparse case was a known gap in the guess's proof map. Their work narrows the hunt for a full proof.

Catalog record

CREATORNevil Anto, Manu Basavaraju, Shashanka Kulamarva
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11281

Browse the full library · About the Tower of Babel