The rich-neighbor chromatic index is linear in the maximum degree
Abstract
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 edge already requires 2D-1 colors in a D-regular graph, where D denotes the maximum degree. We give an upper linear bound chi'_rn(G) <= 6D-8 which holds for every loopless multigraph G with D >= 3, and we show that a coloring realizing this bound can be found in polynomial time. Consequently chi'_rn(G) = Theta(D). For D-regular graphs with D >= 3 the lower bound is 2D-1, and the upper bound is 5D-8. The bound 5D-8 holds more generally for every multigraph with D >= 3 which has a dominating P_{>=3}-system, and we characterize these multigraphs: such a system exists if and only if k_2(G-T) <= 2|T| holds for every set T of vertices, where k_2 counts the components on two vertices. In particular the bound holds for every graph with 3 <= D <= 4d-4, where d denotes the minimum degree. The paper is concluded with a conjecture on the tight upper bound on chi'_rn(G).
Related
- When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
- Bounds on the maximum denominator of fractional chromatic numbers
- Polynomial minimum degree stability for $3$-chromatic graphs
- The Neighbor Graph of Linear Complementary Dual (LCD) Codes
- Linear bounds for rich-neighbor edge-colorings
BibTeX
@misc{kashima2026richneighbor,
title = {{The rich-neighbor chromatic index is linear in the maximum degree}},
author = {Masaki Kashima and Mirko Petruševski and Jelena Sedlar and Riste Škrekovski},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16446},
eprint = {2610.16446},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16446},
}
RIS
TY - UNPB
TI - The rich-neighbor chromatic index is linear in the maximum degree
AU - Masaki Kashima
AU - Mirko Petruševski
AU - Jelena Sedlar
AU - Riste Škrekovski
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16446
UR - https://arxiv.org/abs/2610.16446
AB - 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 edge already requires 2D-1 colors in a D-regular graph, where D denotes the maximum degree. We give an upper linear bound chi'_rn(G) <= 6D-8 which holds for every loopless multigraph G with D >= 3, and we show that a coloring realizing this bound can be found in polynomial time. Consequently chi'_rn(G) = Theta(D). For D-regular graphs with D >= 3 the lower bound is 2D-1, and the upper bound is 5D-8. The bound 5D-8 holds more generally for every multigraph with D >= 3 which has a dominating P_{>=3}-system, and we characterize these multigraphs: such a system exists if and only if k_2(G-T) <= 2|T| holds for every set T of vertices, where k_2 counts the components on two vertices. In particular the bound holds for every graph with 3 <= D <= 4d-4, where d denotes the minimum degree. The paper is concluded with a conjecture on the tight upper bound on chi'_rn(G).
ER -