PreprintCC BY 4.0arXiv
Linear bounds for rich-neighbor edge-colorings
Abstract
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)≤3χ'(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(Km,n)=m+n−1, except that rn(K2,2)=4. For n≥3, rn(Kn)=2n−3, except that rn(K4)=6 and rn(K6)=10. Moreover, for n≥7, the rich edges in every optimal rich-neighbor edge-coloring of Kn form a star forest.
Related
- Rich-neighbor 5-edge-colorings of subcubic graphs whose 3-vertices induce a matching
- The rich-neighbor chromatic index is linear in the maximum degree
- Embedding equitable (s,p)-edge-colorings of Kn
- RACE: Residual-Aware Test-Time Adaptation for Neighbor-Rich Time-Series Foundation Model Forecasting
- Sharp Antipode-Neighbor Bounds in Every Dimension
BibTeX
@misc{kong2026linear,
title = {{Linear bounds for rich-neighbor edge-colorings}},
author = {Jiangxu Kong},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21036},
eprint = {2610.21036},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21036},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Linear bounds for rich-neighbor edge-colorings
AU - Jiangxu Kong
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21036
UR - https://arxiv.org/abs/2610.21036
AB - 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)≤3χ'(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. For n≥3, rn(K_n)=2n−3, except that rn(K_4)=6 and rn(K_6)=10. Moreover, for n≥7, the rich edges in every optimal rich-neighbor edge-coloring of K_n form a star forest.
ER -