{"id":"arxiv/2610.21036","url":"https://arxiv.org/abs/2610.21036","tags":["math.CO"],"score":0,"title":"Linear bounds for rich-neighbor edge-colorings","domain":"math.CO","source":"arxiv","authors":["Jiangxu Kong"],"reviews":0,"subject":"math.CO","summary":"An edge in a proper edge-coloring is rich if all edges adjacent to it receive pairwise distinct colors. A rich-neighbor edge-coloring is a proper edge-coloring in which every non-isolated edge is adjacent to a rich edge. The rich-neighbor chromatic index $\\rn(G)$ is the minimum number of colors in such a coloring. We prove that every loopless multigraph $G$ satisfies $\\rn(G)\\le3χ'(G)$, where $χ'(G)$ is the chromatic index. Exact values are also determined for complete bipartite graphs and complete graphs. For all positive integers $m,n$, $\\rn(K_{m,n})=m+n-1$, except that $\\rn(K_{2,2})=4$.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}