Botler, Colucci and Kohayakawa's additive bound conjecture for the mod kk chromatic index

About 2 years old · traced to

Let GG be a simple graph and let k≥2k\geq 2 be an integer. A χk′\chi'_{k}-coloring of GG is an edge coloring such that the subgraph induced by the edges of each color has all degrees congruent to 1(modk)1\pmod{k}; write χk′(G)\chi'_{k}(G) for the minimum number of colors in such a coloring. Botler, Colucci and Kohayakawa's conjecture. There is a constant CC such that

χk′(G)≤k+C\chi'_{k}(G)\leq k+C

for every graph GG. This conjecture asks whether the linear bound can always have additive constant independent of kk; the paper improves the previously known bound from 198k−101198k-101 to 177k−93177k-93, but does not resolve the conjecture.

References

Primary source

Oothan Nweit and Daqing Yang, “On the mod k chromatic index of graphs”, arXiv:2403.03614 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.