Open Research Index

The rich-neighbor chromatic index is linear in the maximum degree

Masaki Kashima, Mirko Petruševski, Jelena Sedlar, Riste Škrekovski

arXivarxiv/2610.16446Oct 12, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.16446
curl -X POST /api/v1/records/arxiv/2610.16446/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16446/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'