pipette
ESEspañol

Linear bounds for rich-neighbor edge-colorings

Jiangxu Kong

Preprint

In the authors' words

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 is the minimum number of colors in such a coloring. We prove that every loopless multigraph satisfies , where is the chromatic index. Exact values are also determined for complete bipartite graphs and complete graphs. For all positive integers , , except that . For , , except that and . Moreover, for , the rich edges in every optimal rich-neighbor edge-coloring of form a star forest.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.