OpenFrontiers
Join
← Back to the index
OP-12067OpenGraph theory

Coefficient of the acyclic chromatic index (C55C_{55})

Coefficient of the acyclic chromatic index: determine C55C_{55} or improve its bounds; the repository records 1 (lower) and 3.142 (upper).

MSC 05C15 · Coloring of graphs and hypergraphs

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Let GG be a simple graph. The acyclic chromatic index χa′(G)\chi_{a}'(G) of GG is defined to be the least number of colors needed to color the edges of GG so that no two edges coincident on the same vertex are homochromatic and there is no cycle whose edges are colored with only two colors.

Let Δ\Delta be the maximum degree of GG. The coefficient of the acyclic chromatic index, here to be denoted by C55C_{55}, is defined to be the infimum of all cc such that for all GG, χa′(G)≤cΔ+o(Δ)\chi_a'(G) \leq c \Delta +o(\Delta). Easily, 1≤C55.1 \leq C_{55}.

It has been conjectured ([F1978], [ASZ2001]) that for all graphs, the acyclic chromatic index is at most Δ+2.\Delta +2. A consequence of this conjecture would be that C55=1C_{55} =1.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

References (from the repository page)

  • [F1978] J. Fiamčik, The acyclic chromatic class of a graph (in Russian), Math. Slovaca, 28, 139-145, 1978.

  • [ASZ2001] N. Alon, B. Sudakov, and A. Zaks. Acyclic edge colorings of graphs, Journal of Graph Theory, 37(3), 157-167, 2001.

  • [AMR1991] N. Alon, C. McDiarmid, and B. Reed, Acyclic coloring of graphs Random Structures & Algorithms, 2(3), 277-288, 1991.

  • [MR1998] M. Molloy, and B. Reed. Further algorithmic aspects of the local lemma, Proceedings of the thirtieth annual ACM symposium on Theory of computing, 524-529, 1998.

  • [NPS2012] S. Ndreca, A. Procacci, B. Scoppola, Improved bounds on coloring of graphs Eur. J. of Comb., 33(4), 592-609, 2012.

  • [EP2013] L. Esperet, and A. Parreau, Acyclic edge-coloring using entropy compression, Eur. J. Comb., 34(6), 1019--1027, 2013.

  • [GKPT2017] I. Giotis, L. Kirousis, K.I. Psaromiligkos, and D.M. Thilikos, Acyclic edge coloring through the Lovász local lemma. Theoretical Computer Science, 665, 40-50, 2017, Correction in: arXiv 1407.5374.

  • [GKZ2018] G. Gutowski, J. Kozik, and X. Zhu. Acyclic edge coloring using entropy compression, Abstracts of the 7th Polish Combinatorial Conference, 2018. Available: here.

  • [FLM2020] P.M.S Fialho, B.N.B de Lima, and A. Procacci, A new bound on the acyclic edge chromatic number, Discrete Mathematics, 343(11), 112037, 2020.

  • [KLS2026] L. Kirousis, J. Livieratos, and A. Singh, arXiv 2602.14859, 2026.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 1; best known upper bound 3.142. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
16 [AMR1991], [MR1998]
9.62 [NPS2012]
4 [EP2013]
3.74 [GKPT2017]
4- [GKZ2018]
3.569 [FLM2020]
3.142 [KLS2026]

Known lower bounds

Bound Reference Comments
1 Trivial conjectured to be sharp
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Coefficient of the acyclic chromatic index ($C_{55}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.