Upper bounds on the uniquely restricted chromatic index

Golumbic, Hirst, and Lewenstein define a matching in a simple, finite, and undirected graph G to be uniquely restricted if no other matching covers exactly the same set of vertices. We consider uniquely restricted edge‐colorings of G , defined as partitions of its edge set into uniquely restricted matchings, and study the uniquely restricted chromatic index χ ′ u r( G )of G , defined as the minimum number of uniquely restricted matchings required for such a partition. For every graph G ,χ ′ ( G ) ≤ a ′ ( G ) ≤ χ ′ u r( G ) ≤ χ ′ s( G ) ,where χ ′ ( G ) is the classical chromatic index, a ′ ( G ) the acyclic chromatic index, and χ ′ s( G )the strong chromatic index of G . While Vizing's famous theorem states that χ ′ ( G ) is either the maximum degree Δ ( G ) of G or Δ ( G ) + 1 , two famous open conjectures due to Alon, Sudakov, and Zaks, and to Erdős and Nešetřil concern upper bounds on a ′ ( G ) and χ ′ s( G )in terms of Δ ( G ) . Since χ ′ u r( G )is sandwiched between these two parameters, studying upper bounds in terms of Δ ( G ) is a natural problem. We show that χ ′ u r( G ) ≤ Δ ( G ) 2with equality if and only if some component of G is K Δ ( G ) , Δ ( G ). If G is connected, bipartite, and distinct from K Δ ( G ) , Δ ( G ), and Δ ( G ) is at least 4 , then, adapting Lovász's elegant proof of Brooks’ theorem, we show that χ ′ u r( G ) ≤ Δ ( G ) 2 − Δ ( G ) . Our proofs are constructive and yield efficient algorithms to determine the corresponding edge‐colorings.