Skip to Main content Skip to Navigation
Journal articles

Upper bounds on the uniquely restricted chromatic index

Julien Baste 1 Dieter Rautenbach 2 Ignasi Sau Valls 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 χ′ur(G) of G, defined as the minimum number of uniquely restricted matchings required for such a partition. For every graph G, χ′(G) ≤ a′(G) ≤ χ′ur(G) ≤ χ′s(G), where χ′(G) is the classical chromatic index, a′(G) is the acyclic chromatic index, and χ′s(G) is the strong chromatic index of G, respectively. 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 Erdo ̋s and Neˇsetˇril concern upper bounds on a′(G) and χ′s(G) in terms of ∆(G). Since χ′ur(G) is sandwiched between these two parameters, studying upper bounds in terms of ∆(G) is a natural problem. We show that χ′ur(G) ≤ ∆(G)2 with 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 Lova ́sz’s elegant proof of Brooks’ theorem, we show that χ′ur (G) ≤ ∆(G)2 − ∆(G). Our proofs are constructive and yield efficient algorithms to determine the corresponding edge-colorings.
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download
Contributor : Ignasi Sau <>
Submitted on : Sunday, December 15, 2019 - 4:03:52 PM
Last modification on : Wednesday, December 18, 2019 - 1:49:03 AM
Document(s) archivé(s) le : Monday, March 16, 2020 - 1:53:32 PM




Julien Baste, Dieter Rautenbach, Ignasi Sau Valls. Upper bounds on the uniquely restricted chromatic index. Journal of Graph Theory, Wiley, 2018, 91 (3), pp.251-258. ⟨10.1002/jgt.22429⟩. ⟨lirmm-02412578⟩



Record views


Files downloads