{"id":"arxiv/2610.16446","url":"https://arxiv.org/abs/2610.16446","tags":["math.CO"],"score":0,"title":"The rich-neighbor chromatic index is linear in the maximum degree","domain":"math.CO","source":"arxiv","authors":["Masaki Kashima","Mirko Petruševski","Jelena Sedlar","Riste Škrekovski"],"reviews":0,"subject":"math.CO","summary":"An edge of a multigraph is rich with respect to a proper edge-coloring if all the edges adjacent to it receive mutually distinct colors, and a proper edge-coloring is a rich-neighbor coloring if every non-isolated edge has a rich edge adjacent to it. The least number of colors in such a coloring is the rich-neighbor chromatic index chi'_rn(G). So far it was studied for subcubic graphs only, and multigraphs of larger maximum degree are considered here for the first time. The only upper bound valid in general was the quadratic one inherited from the strong chromatic index, while a single rich…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}