Upper bounds on the uniquely restricted chromatic index |
| |
Authors: | Julien Baste Dieter Rautenbach Ignasi Sau |
| |
Institution: | 1. CNRS, LIRMM, Université de Montpellier, Montpellier, France;2. Institute of Optimization and Operations Research, Ulm University, Ulm, Germany |
| |
Abstract: | Golumbic, Hirst, and Lewenstein define a matching in a simple, finite, and undirected graph to be uniquely restricted if no other matching covers exactly the same set of vertices. We consider uniquely restricted edge-colorings of , defined as partitions of its edge set into uniquely restricted matchings, and study the uniquely restricted chromatic index of , defined as the minimum number of uniquely restricted matchings required for such a partition. For every graph , where is the classical chromatic index, the acyclic chromatic index, and the strong chromatic index of . While Vizing's famous theorem states that is either the maximum degree of or , two famous open conjectures due to Alon, Sudakov, and Zaks, and to Erd?s and Ne?et?il concern upper bounds on and in terms of . Since is sandwiched between these two parameters, studying upper bounds in terms of is a natural problem. We show that with equality if and only if some component of is . If is connected, bipartite, and distinct from , and is at least , then, adapting Lovász's elegant proof of Brooks’ theorem, we show that . Our proofs are constructive and yield efficient algorithms to determine the corresponding edge-colorings. |
| |
Keywords: | acyclic chromatic index chromatic index edge-coloring strong chromatic index uniquely restricted matching |
|
|