An improvement on the bound for the acyclic chromatic index
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914332886958080 |
|---|---|
| author | Kirousis, Lefteris Livieratos, John Singh, Alexandros |
| author_facet | Kirousis, Lefteris Livieratos, John Singh, Alexandros |
| contents | The acyclic chromatic index (or acyclic edge-chromatic number) of a graph is the least number of colors needed to properly color its edges so that none of its cycles has only two colors. We show that for a graph of max degree $Δ$, the acyclic chromatic index is at most $3.142(Δ-1)+1$, improving on the (best to date) bound of Fialho et al. (2020). Our improvement is made possible by considering unordered (non-plane) trees, instead of ordered (plane) ones, as witness structures for the Lovász Local Lemma, a key combinatorial tool often used in related works. The counting of these witness structures entails methods of Analytic Combinatorics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14859 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An improvement on the bound for the acyclic chromatic index Kirousis, Lefteris Livieratos, John Singh, Alexandros Combinatorics Discrete Mathematics The acyclic chromatic index (or acyclic edge-chromatic number) of a graph is the least number of colors needed to properly color its edges so that none of its cycles has only two colors. We show that for a graph of max degree $Δ$, the acyclic chromatic index is at most $3.142(Δ-1)+1$, improving on the (best to date) bound of Fialho et al. (2020). Our improvement is made possible by considering unordered (non-plane) trees, instead of ordered (plane) ones, as witness structures for the Lovász Local Lemma, a key combinatorial tool often used in related works. The counting of these witness structures entails methods of Analytic Combinatorics. |
| title | An improvement on the bound for the acyclic chromatic index |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2602.14859 |