Uniquely restricted matchings
and edge colorings
Julien Baste1 , Dieter Rautenbach2 , and Ignasi Sau1,3
1

arXiv:1611.06815v1 [math.CO] 21 Nov 2016

2

CNRS, LIRMM, Université de Montpellier, Montpellier, France
baste@lirmm.fr, sau@lirmm.fr
Institute of Optimization and Operations Research, Ulm University, Ulm, Germany
dieter.rautenbach@uni-ulm.de
3
Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil

Abstract. A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by
Golumbic, Hirst, and Lewenstein and studied in a number of articles.
Our contribution is twofold. We provide approximation algorithms for
computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of 9/5 for subcubic bipartite graphs, improving over a 2-approximation algorithm proposed by
Mishra. Furthermore, we study the uniquely restricted chromatic index of
a graph, defined as the minimum number of uniquely restricted matchings into which its edge set can be partitioned. We provide tight upper
bounds in terms of the maximum degree and characterize all extremal
graphs. Our constructive proofs yield efficient algorithms to determine
the corresponding edge colorings.
Keywords: uniquely restricted matching; bipartite graph; approximation algorithm; edge coloring; subcubic graph.

1

Introduction

Matchings in graphs are among the most fundamental and well-studied objects
in combinatorial optimization [25, 32]. While classical matchings lead to many
efficiently solvable problems, more restricted types of matchings [30] are often
intractable; induced matchings [3, 6, 7, 10, 11, 15, 18–20, 26] being a prominent
example. Here we study the so-called uniquely restricted matchings, which were
introduced by Golumbic, Hirst, and Lewenstein [14] and studied in a number
of papers [13, 21–23, 27, 29]. We also consider the corresponding edge coloring
notion.
Before we explain our contribution and discuss related research, we collect
some terminology and notation (cf. e.g. [8] for undefined terms). We consider
finite, simple, and undirected graphs. A matching in a graph G [25] is a set of
pairwise non-adjacent edges of G. For a matching M , let V (M ) be the set of
vertices incident with an edge in M . A matching M in a graph G is induced [10]
if the subgraph G[V (M )] of G induced by V (M ) is 1-regular. Golumbic, Hirst,
and Lewenstein [14] define a matching M in a graph G to be uniquely restricted
if there is no matching M 0 in G with M 0 6= M and V (M 0 ) = V (M ), that is, no
other matching covers exactly the same set of vertices. It is easy to see that a
matching M in G is uniquely restricted if and only if there is no M -alternating

2

Julien Baste, Dieter Rautenbach, and Ignasi Sau

cycle in G, which is a cycle in G that alternates between edges in M and edges
not in M . Let the matching number ν(G), the strong matching number νs (G),
and the uniquely restricted matching number νur (G) of G be the maximum size
of a matching, an induced matching, and a uniquely restricted matching in G,
respectively. Since every induced matching is uniquely restricted, we obtain
νs (G) ≤ νur (G) ≤ ν(G)
for every graph G.
Each type of matching naturally leads to an edge coloring notion. For a graph
G, let χ0 (G) be the chromatic index of G, which is the minimum number of matchings into which the edge set E(G) of G can be partitioned. Similarly, let the strong
chromatic index χ0s (G) [11] and the uniquely restricted chromatic index χ0ur (G) of
G be the minimum number of induced matchings and uniquely restricted matchings into which the edge set of G can be partitioned, respectively. A partition of
the edges of a graph G into uniquely restricted matchings is a uniquely restricted
edge coloring of G. Another related notion are acyclic edge colorings, which are
partitions of the edge set into matchings such that the union of every two of
the matchings is a forest. The minimum number of matchings in an acyclic edge
coloring of a graph G is its acyclic chromatic index a0 (G) [1, 12]. Exploiting the
obvious relations between the different edge coloring notions, we obtain
χ0 (G) ≤ a0 (G) ≤ χ0ur (G) ≤ χ0s (G)

(1)

for every graph G.
Stockmeyer and Vazirani [30] showed that computing the strong matching number is NP-hard. Their result was strengthened in many ways, and also restricted
graph classes where the strong matching number can be determined efficiently
were studied [3, 6, 7, 26]. Golumbic, Hirst, and Lewenstein [14] showed that it is
NP-hard to determine νur (G) for a given bipartite or split graph G. Mishra [27]
strengthened this by showing that it is not possible to approximate νur (G) within
1
a factor of O(n 3 − ) for any  > 0, unless NP=ZPP, even when restricted to bipartite, split, chordal or comparability graphs of order n. Furthermore, he showed
that νur (G) is APX-complete for subcubic bipartite graphs.
On the positive side, Golumbic, Hirst, and Lewenstein [14] described efficient algorithms that determine νur (G) for cacti, threshold graphs, and proper
interval graphs. Solving a problem from [14], Francis, Jacob, and Jana [13] described an efficient algorithm for νur (G) in interval graphs. Solving yet another
problem from [14], Penso, Rautenbach, and Souza [29] showed that the graphs
G with ν(G) = νur (G) can be recognized in polynomial time. Complementing
his hardness results, Mishra [27] proposed a 2-approximation algorithm for cubic
bipartite graphs.
While χ0 (G) of a graph G of maximum degree ∆ is either ∆ or ∆ + 1 [31],
Erdős and Nešetřil [11] conjectured χ0s (G) ≤ 45 ∆2 , and much of the research on
the strong chromatic index is motivated by this conjecture. Building on earlier
work of Molloy and Reed [28], Bruhn and Joos [4] showed χ0s (G) ≤ 1.93∆2
provided that ∆ is sufficiently large. For further results on the strong chromatic
index we refer to [2, 11, 16, 17].
Fiamčik [12] and Alon, Sudakov, and Zaks [1] conjectured that every graph of
maximum degree ∆ has an acyclic edge coloring using no more than ∆ + 2 colors.

Uniquely restricted matchings and edge colorings

3

See [5, 9] for further references and the currently best known results concerning
general graphs and graphs of large girth.
In view of the famous open conjectures on χ0s (G) and a0 (G), the inequality
chain (1) motivates to study upper bounds on χur (G) in terms of the maximum
degree ∆ of a graph G.
Our contribution is twofold. We present approximations algorithms for νur (G) in
some bipartite graphs in Sections 2-3, and tight bounds on χ0ur (G) in Section 4.
Concerning the algorithms, improving on Mishra’s 2-approximation algorithm [27], we describe in Section 3 a 9/5-approximation algorithm for computing
νur (G) of a given bipartite subcubic graph G. This algorithm requires some complicated preprocessing based on detailed local analysis. In order to illustrate our
general approach in a cleaner setting, we first describe in Section 2 algorithms
for C4 -free bipartite graphs of arbitrary maximum degree.
Concerning the uniquely restricted chromatic index, we achieve best-possible
upper bounds in terms of the maximum degree, and even characterize all extremal
graphs. Since our proofs are constructive, it is easy to extract efficient algorithms
finding the corresponding edge colorings.
We conclude with some open problems in Section 5.

2

Approximation algorithms for C4 -free bipartite graphs

Before we proceed to present the 9/5-approximation algorithm for subcubic bipartite graphs in Section 3, we first describe in this section an approximation
algorithm for the C4 -free case. The proof of the next lemma contains the main
algorithmic ingredients. Note that the size of the smaller partite set in a bipartite
graph is always an upper bound on the uniquely restricted matching number.
For an integer k, let [k] denote the set of positive integers between 1 and k.
For a graph G, let n(G) denote its number of vertices.
Lemma 1. Let ∆ ≥ 3 be an integer. If G is a connected C4 -free bipartite graph
of maximum degree at most ∆ with partite sets A and B such that every vertex in
A has degree at least 2, and some vertex in B has degree less than ∆, then G has
(∆−1)2 +(∆−2)
a uniquely restricted matching M of size at least (∆−1)
3 +(∆−2) |A|. Furthermore,
such a matching can be found in polynomial time.
Proof: We give an algorithmic proof of the lower bound such that the running
time of the corresponding algorithm is polynomial in n(G), which immediately
implies the second part of the statement. Therefore, let G be as in the statement.
Throughout the execution of our algorithm, as illustrated in Fig. 1, we maintain
a pair (U, M ) such that
(a)
(b)
(c)
(d)
(e)

U is a subset of V (G),
M is a uniquely restricted matching with V (M ) ⊆ U ,
no vertex in B ∩ U has a neighbor in A \ U ,
no vertex in B \ U has all its neighbors in A ∩ U ,
if
s vertices in A ∩ U are incident with an edge in M ,
d vertices in A ∩ U are not incident with an edge in M but have a neighbor
in B \ U , and

4

Julien Baste, Dieter Rautenbach, and Ignasi Sau

f vertices in A∩U are neither incident with an edge in M nor have a neighbor
in B \ U , then


(∆ − 1)2 (∆ − 2)s − (d + f ) ≥ (∆ − 2)f.
(2)
s

f

d

A

M

B

U

Fig. 1. Example for ∆ = 3 of the parameters defined in the proof of Lemma 1.
The set U is dashed, and the uniquely restricted matching M corresponds to the
thicker edges.
Initially, let U and M be empty sets. Note that properties (a) to (e) hold.
As long as U is a proper subset of V (G), we iteratively replace the pair (U, M )
with a pair (U 0 , M 0 ) such that U is a proper subset of U 0 , M is a proper subset
of M 0 , and properties (a) to (e) hold for (U 0 , M 0 ). Let s0 , d0 , and f 0 denote the
updated values considered in (e). Once U = V (G), we have s = |M |, d = 0, and
f = |A| − |M |, and (2) implies the stated lower bound on |M |.
We proceed to the description of the extension operations. Therefore, suppose
that U is a proper subset of V (G). Since G is connected, and some vertex in B
has degree less than ∆, some vertex u in B \ U has less than ∆ neighbors in
A \ U , that is, if dŪ (u) = |NG (u) \ U |, then 1 ≤ dŪ (u) ≤ ∆ − 1, where the first
inequality follows from property (d). We choose u ∈ B \ U such that dŪ (u) is as
small as possible.
Case 1: dŪ (u) = 1.
Let v be the unique neighbor of u in A \ U . Let {u1 , . . . , uk } be the set of
all vertices u in B \ U with NG (u) \ U = {v}, and note that 1 ≤ k ≤ ∆. Let
U 0 = U ∪{u1 , . . . , uk , v}. For some integer ` ≤ k, we may assume that {u1 , . . . , u` }
is the set of those ui with i ∈ [k] such that ui has a neighbor in A ∩ U , and no
neighbor of ui in A ∩ U is incident with M . Note that every vertex ui with
i ∈ [k] \ [`] either has no neighbor in A ∩ U or has some neighbor in A ∩ U that
is incident with M .
First, suppose that ` ≥ 2. Let M 0 arise from M by adding, for every i ∈ [`], an
edge between ui and a neighbor wi of ui in A∩U . Note that all these neighbors wi
in A∩U are distinct. Indeed, if two vertices ui and uj have a common neighbor w
in A ∩ U , then the set of vertices {v, ui , uj , w} would induce a C4 in G. Note also
that M 0 is indeed a uniquely restricted matching, as if there exists an edge ui wj

Uniquely restricted matchings and edge colorings

5

with i, j ∈ [`] and i 6= j that could potentially create an M 0 -alternating cycle,
then the set of vertices {v, ui , uj , wj } would again induce a C4 in G. Clearly,
replacing (U, M ) with (U 0 , M 0 ), we maintain properties (a) to (d), and s0 = s + `.
Let nd be the number of vertices in A ∩ U that are not incident with an edge
in M 0 , have a neighbor in B \ U , but do not have a neighbor in B \ U 0 ; note
that each such vertex has a neighbor in the set {u1 , . . . , uk }. As every vertex
in {u1 , . . . , uk } is neighbor of v and of a vertex incident with an edge in M 0 ,
it holds that nd ≤ k(∆ − 2) ≤ ∆(∆ − 2). If v has a neighbor in B \ U 0 , then
d0 = d−nd +1 and f 0 = f +nd , and, if v has no neighbor in B\U 0 , then d0 = d−nd
and f 0 = f + nd + 1. In both cases d0 + f 0 = d + f + 1 and f 0 ≤ f + nd + 1. Since
(∆−1)2
(∆ − 2)` − 1 ≥ ∆(∆ − 2) + 1 ≥ nd + 1, property (e) is maintained.
∆−2
Next, suppose that ` ≤ 1. Let M 0 arise from M by adding the edge u1 v.
Clearly, replacing (U, M ) with (U 0 , M 0 ), we maintain properties (a) to (d), and
s0 = s + 1. Defining nd exactly as above, we obtain nd ≤ k(∆ − 2) + ` ≤
2
∆(∆−2)+1, d0 = d−nd , and f 0 = f +nd . Since (∆−1)
∆−2 (∆−2) ≥ ∆(∆−2)+1 ≥ nd ,
property (e) is maintained.
Case 2: 2 ≤ dŪ (u) ≤ ∆ − 1.
Let {v1 , . . . , vk } = NG (u) \ U and let U 0 = U ∪ {u, v1 , . . . , vk }. Note that 2 ≤
k ≤ ∆ − 1.
First, suppose that u has a neighbor v in A ∩ U , and that no neighbor of
u in A ∩ U is incident with M . Let M 0 arise from M by adding the edge uv.
Clearly, replacing (U, M ) with (U 0 , M 0 ), we maintain properties (a) to (c), and
s0 = s + 1. Let us prove that property (d) is also maintained. Since G has
no C4 and k ≥ 2, no vertex in B \ U that is distinct from u can have more
than one neighbor among v1 , . . . , vk . Since we are in Case 2, every vertex in
B \ U has more than one neighbor in A \ U , hence property (d) remains true.
Similarly as above, let nd be the number of vertices in A∩U that are not incident
with an edge in M 0 , have a neighbor in B \ U , but do not have a neighbor in
B \ U 0 .Note that nd ≤ ∆− k − 1, d0 = d + k − nd − 1, and f 0 = f + nd . Since
(∆−1)2
∆−2

(∆ − 2) − (k − 1) ≥ ∆ − k − 1 ≥ nd , property (e) is maintained.
Next, suppose that u either has no neighbor in A ∩ U or some neighbor of
u in A ∩ U is incident with M . Let M 0 arise from M by adding the edge uv1 .
Clearly, replacing (U, M ) with (U 0 , M 0 ), we again maintain properties (a) to (d),
and s0 = s + 1. Note that, in the case where u has a neighbor in A ∩ U , v1 does
not have neighbors in M because of property (c), which guarantees that M 0 is
indeed a uniquely restricted matching. Defining nd exactly as above, we obtain
nd ≤ ∆ − k − 1. Indeed, if u has no neighbor in A ∩ U , then nd = 0. On the other
hand, if u has a neighbor in A ∩ U that is incident with M , then nd ≤ ∆ − k − 1.
As k ≤ ∆ − 1, in both cases it holds that nd ≤ ∆ − k − 1. Also, we get that
d0 = d + k − nd + 1 and f 0 = f + nd , and the same calculation as above implies
that property (e) is maintained.

Since the considered cases exhaust all possibilities, and in each case we described
an extension that maintains the relevant properties, the proof is complete up to
the running time of the algorithm, which we proceed to analyze. One can easily
check that each extension operation takes time O(∆n), where n = n(G). As in
each extension operation, the size of U is incremented by at least one, it follows
that the overall running time of the algorithm is O(∆n2 ).
2

6

Julien Baste, Dieter Rautenbach, and Ignasi Sau

With Lemma 1 at hand, we proceed to our first approximation algorithm.
Theorem 1. Let ∆ ≥ 3 be an integer. For a given connected C4 -free bipartite graph G of maximum degree at most ∆, one can find in polynomial time a
2
+(∆−2)
uniquely restricted matching M of G of size at least (∆−1)
(∆−1)3 +(∆−2) νur (G).
2

(∆−1) +(∆−2)
Proof: Let α = (∆−1)
3 +(∆−2) and let G be the set of all C4 -free bipartite graphs
G of maximum degree at most ∆ such that every component of G has a vertex
of degree less than ∆. First, we prove that, for every given graph G in G, one
can find in polynomial time a uniquely restricted matching M of size at least
ανur (G). Therefore, let G be in G.
If G has a vertex u of degree 1, and v is the unique neighbor of u, then let
G0 = G − {u, v}. Clearly, νur (G0 ) ≥ νur (G) − 1, and if M 0 is a uniquely restricted
matching of G0 , then M 0 ∪ {uv} is a uniquely restricted matching of G. Note that
G0 belongs to G. Let G00 be the graph obtained from G0 by removing every isolated
vertex. Clearly, νur (G00 ) ≥ νur (G0 ), if M 00 is a uniquely restricted matching of
G00 , then M 00 is a uniquely restricted matching of G0 , and G00 belongs to G.
Iteratively repeating these reductions, we efficiently obtain a set M1 of edges
of G as well as a subgraph G2 of G such that G2 ∈ G, νur (G2 ) ≥ νur (G) − |M1 |,
M1 ∪ M2 is a uniquely restricted matching of G for every uniquely restricted
matching M2 of G2 , and either n(G2 ) = 0 or δ(G2 ) ≥ 2. Note that if G has
minimum degree at least 2, then we may choose M1 empty and G2 equal to G.
Now, by suitably choosing the bipartition of each component K of G2 , and applying Lemma 1 to K, one can determine in polynomial time a uniquely restricted
matching M2 of G2 with |M2 | ≥ ανur (G2 ). Since the set M1 ∪ M2 is a uniquely
restricted matching of G of size at least |M1 | + ανur (G2 ) ≥ |M1 | + α(νur (G) −
|M1 |) ≥ ανur (G), the proof of our claim about G is complete.
Now, let G be a given connected C4 -free bipartite graph G of maximum degree
at most ∆. If G is not ∆-regular, then G ∈ G, and the desired statement already
follows. Hence, we may assume that G is ∆-regular, which implies that its two
partite sets A and B are of the same order. By [29], we can efficiently decide
whether νur (G) = ν(G). Furthermore, if νur (G) = ν(G), then, again by [29], we
can efficiently determine a maximum matching that is uniquely restricted. Hence,
we may assume that νur (G) < ν(G). This implies that νur (G) < |A|, and, hence,
there is some vertex u ∈ V (G) with νur (G − u) = νur (G). Since G − u ∈ G for
every vertex u of G, considering the n(G) induced subgraphs G − u for u ∈ V (G),
one can determine in polynomial time a uniquely restricted matching M of G
with |M | ≥ max{ανur (G − u) : u ∈ V (G)} = ανur (G). The desired statement
follows.
2

3

A 9/5-approximation for subcubic bipartite graphs

We show that – at least for ∆ = 3 – C4 -freeness is not an essential assumption.
Namely, this section is devoted to proving the following theorem.
Theorem 2. For a given connected subcubic bipartite graph G, one can find in
polynomial time a uniquely restricted matching of G of size at least 95 νur (G).

Uniquely restricted matchings and edge colorings

7

We believe that Theorem 2 extends to larger maximum degrees, that is, the
conclusion of Theorem 1 should hold without the assumption of C4 -freeness.
In order to ease the presentation, in this section we will use figures to describe
some of the “patterns” considered by the algorithms. More formally, given a graph
G, a pattern P is a subgraph of G in which the set of vertices that have neighbors
in V (G) \ V (P ) is fixed.
In all these figures, the partition of the corresponding bipartite subcubic graph
into two sets A and B is represented by using squares and circles, respectively.
The half-edges specify which vertices in a pattern have neighbors outside of it.
The following lemma is crucial in order to prove Theorem 2; it plays a role
similar to the one played by Lemma 1 for proving Theorem 1.

x
x
x
e1

e2

y
⇓

⇓

⇓

(i) Pattern R.1.

(ii) Pattern R.2.
y

(iii) Pattern R.3.
y

x

x

y

x

z
⇓

⇓

⇓

(iv) Pattern R.4.

(v) Pattern R.5.

(vi) Pattern R.6.

Fig. 2. The six forbidden patterns.

8

Julien Baste, Dieter Rautenbach, and Ignasi Sau

Lemma 2. If G is a connected subcubic bipartite graph with partite sets A and
B such that
(1) G does not any of the patterns R.1, R.2, R.3, R.4, R.5, or R.6 depicted in
Fig. 2,
(2) G does not contain two vertices with the same neighborhood,
(3) each vertex of G has degree at least 2, and
(4) some vertex in B has degree at most 2,
then a uniquely restricted matching M of G of size at least 59 νur (G) can be found
in polynomial time.
Proof: If n(G) ≤ 10, then we solve the problem optimally by brute force (we
will see that the largest pattern without neighbors outside of it considered in the
proof has 10 vertices). Therefore, we assume henceforth that G contains at least
11 vertices. In the following, we look for a uniquely restricted matching M of
size at least 95 |A|. As |A| ≥ νur (G), this implies the desired result. We define two
types of C4 , namely C41 and C42 , as follows. A C41 is a subgraph of G isomorphic
to a C4 such that if V (C41 ) ∩ A = {a1 , a2 }, then dG (a1 ) = 3 and dG (a2 ) = 2. A
C42 is a subgraph of G isomorphic to a C4 such that if V (C42 ) ∩ A = {a1 , a2 },
then dG (a1 ) = dG (a2 ) = 3. Note that because of condition (2), there is no
subgraph G0 of G isomorphic to C4 such that if V (G0 ) ∩ A = {a1 , a2 }, then
dG (a1 ) = dG (a2 ) = 2, as it implies that a1 and a2 have the same neighborhood.
Similarly to the proof of Lemma 1, throughout the execution of our algorithm
we maintain a triple (U, M, γ) that respects the following properties:
U ⊆ V (G),
M is a uniquely restricted matching of G such that V (M ) ⊆ U ,
γ : U ∩ A → {>, `, ⊥},
for every v ∈ A ∩ U , γ(v) = > if and only if v ∈ V (M ) and γ(v) =` only if
that v has at least one neighbor in B \ U ,
(e) there is no edge between vertices in U ∩ B and vertices in A \ U ,
(f) every vertex in B \ U has at least one neighbor in A \ U ,
(g) if s = |{v ∈ A : γ(v) = >}|, d = |{v ∈ A : γ(v) =`}|, and f = |{v ∈ A :
γ(v) = ⊥}|, then
4 (s − (d + f )) ≥ f, and
(3)

(a)
(b)
(c)
(d)

(h) for each C41 G0 in G \ U , there is no vertex v in NG (V (G0 )) ∩ U ∩ A such that
γ(v) =`.
We initialize the algorithm with U = ∅, M = ∅, and γ = ∅. Note that
properties (a) to (h) are satisfied.
In the first part of the algorithm, we focus on removing the C4 ’s from G \ U .
For this we first take care the C41 ’s in G \ U , and then we deal with the C42 ’s.
As long as G \ U is not empty, we consider the first of the following cases such
that the corresponding condition is fulfilled, where dŪ (u) = |NG (u) \ U |:
•
•
•
•

Case
Case
Case
Case

1:
2:
3:
4:

there
there
there
there

exists
exists
exists
exists

u ∈ B \ U such that dŪ (u) = 1.
G0 , a C41 in G \ U .
G0 , a C42 in G \ U .
u ∈ B \ U such that dŪ (u) = 2.

Uniquely restricted matchings and edge colorings

9

Note that, by property (e) and the connectivity of G, we know that, as long
as G \ U is not the empty graph, at least one of these four cases should apply.
We study each case and show that for each of them, we can find a new triple
(U 0 , M 0 , γ 0 ) starting from (U, M, γ) such that U is a proper subset of U 0 , M is
a proper subset of M 0 , γ is the restriction of γ 0 to U , and properties (a) to (h)
hold for (U 0 , M 0 , γ 0 ), where s0 , d0 , and f 0 denote the updated values considered
in (g). Once U = V (G), we have s = |M |, d = 0, and f = |A| − |M |, and (3)
implies that |M | ≥ 95 |A|.
In order to prove that such a triple can indeed be found in polynomial time,
we distinguish four cases.
In the following, by resolving a pattern P we mean that from a triple (U, M, γ)
that respects properties (a) to (h) such that U ∩ V (P ) = ∅, we exhibit a triple
(U 0 , M 0 , γ 0 ) that also respects properties (a) to (h) and such that U 0 = U ∪ V (P ).
Case 1: there exists u ∈ B \ U such that dŪ (u) = 1.
Assume that dŪ (u) = 1 and let v be the only neighbor of u in A \ U . Let
{ui : i ∈ [k]} be the set of all vertices u in B \ U with NG (u) \ U = {v}. Note
that 1 ≤ k ≤ 3. Let U 0 = U ∪ {v} ∪ {ui : i ∈ [k]}. By construction of G, we
know that every vertex ui , i ∈ [k], is of degree at least 2 in G, so it has at least
one neighbor in A ∩ U . For every i ∈ [k], we define Wi = NG (ui ) ∩ U . Note
that forSi, j ∈ [k] with i 6= j, Wi and Wj can intersect. Let nd be the number
|{w ∈ i∈[k] Wi : γ(w) =`}|. Note that for each ui , i ∈ [k], v ∈ NG (ui ) and
v 6∈ U . This implies that for each i ∈ [k], |Wi | ≤ 2, and so, nd ≤ 6.
First, assume that nd ≤ 4. Let M 0 arise from M by addingSthe edge u1 v.
Let γ 0 be obtained from γ where γ 0 (v) = >, and for each w ∈ i∈[k] Wi , such
that γ(w) =`, then γ 0 (w) = ⊥. Clearly, replacing (U, M, γ) with (U 0 , M 0 , γ 0 ), we
maintain properties (a) to (f). By construction of γ 0 , we have that s0 = s + 1,
d0 = d − nd , and f 0 = f + nd . As nd ≤ 4, property (g) is maintained. Note that
γ 0−1 (`) ⊆ γ −1 (`). This implies that property (h) is maintained.
Assume now that nd ≥ 5. This implies that k = 3, and two sets of {Wi :
i ∈ [k]}, say W1 and W2 , are such that {w ∈ W1 ∪ W2 : γ(w) 6=`} = ∅ and
|W1 | = |W2 | = 2. Because of condition (2), we know that we can find w1 ∈ W1 \W2
and w2 ∈ W2 \ W1 . Let M 0 arise from M by adding the edges
u1 w1 and u2 w2 .
S
Let γ 0 be obtained from γ where γ 0 (v) = ⊥, for each w ∈ ( i∈[k] Wi ) \ {w1 , w2 },
such that γ(w) =`, then γ 0 (w) = ⊥ and γ 0 (w1 ) = γ 0 (w2 ) = >. Note that M 0 is
a uniquely restricted matching. Clearly, replacing (U, M, γ) with (U 0 , M 0 , γ 0 ), we
maintain properties (a) to (f). Then by construction of γ 0 we obtain that s0 = s+2,
d0 = d − nd , and f 0 = f + nd − 2 + 1. We obtain that s0 − (d0 + f 0 ) = s − (d + f ) + 3.
As, nd ≤ 6, property (g) is maintained. Note that γ 0−1 (`) ⊆ γ −1 (`). This implies
that property (h) is maintained.
Case 2: there exists a C41 G0 in G \ U .
We assume in this case that for every u ∈ B \ U , dŪ (u) ≥ 2. Let V (G0 ) ∩ A =
{a1 , a2 } such that dG (a1 ) = 3 and V (G0 ) ∩ B = {b1 , b2 }. For this case, when we
say that we define M 0 and γ 0 by updating the values of M and γ according to a
figure, it means that we add to M every red edge of the figure and for every v
of A that is depicted in the figure, then γ 0 (v) = > if v is the endpoint of a red
edge, and γ 0 (v) = ⊥ otherwise.

10

Julien Baste, Dieter Rautenbach, and Ignasi Sau

First, assume that NG (b1 ) \ U = NG (b2 ) \ U = {a1 , a2 }. If the only vertex
of NG (a1 ) \ V (G0 ) is inside another C4 , then we are in the situation depicted
in Fig. 3(ii) and we define U 0 to be the union of U and the vertices of the two
C4 ’s, and we define M 0 and γ 0 by updating the values of M and γ according to
Fig. 3(ii). Otherwise, we are in the situation depicted in Fig. 3(i), we define U 0
to be U ∪ V (G0 ), and we define M 0 and γ 0 by updating the values of M and γ
according to Fig. 3(i). In both cases, one can see that properties (a) to (h) are
maintained.

(i) Not attached to a C4 .

(ii) Attached to a C4 .

Fig. 3. First case of C41 .

Secondly, assume that there exists a3 ∈ A \ U such that a3 ∈ NG (b2 ) and
a3 6∈ NG (b1 ). If there exists b3 with neighbors only in U ∪ V (G) ∪ {a3 }, then we
define U 0 to be the union of U and {a1 , a2 , a3 , b1 , b2 , b3 }, and we define M 0 and
γ 0 by updating the values of M and γ according to Fig. 4(ii). Otherwise, we are
in the situation depicted in Fig. 4(i), we define U 0 to be U ∪ V (G0 ) ∪ {a3 }, and
we define M 0 and γ 0 by updating the values of M and γ according to Fig. 4(i).
In both cases we can see that properties (a) to (h) are maintained.

(i) If b3 does not exist.

(ii) If b3 exists.

Fig. 4. Second case of C41 .

Uniquely restricted matchings and edge colorings

Pattern (i).
Pattern (ii).

Pattern (iii).

Pattern (iv).

Pattern (v).

Pattern (vi).

Pattern (vii).

Pattern (viii).

Pattern (ix).

Pattern (x).

Pattern (xi).

Pattern (xii).

Pattern (xiii).

Fig. 5. Third case of C41 .

11

12

Julien Baste, Dieter Rautenbach, and Ignasi Sau

Third, assume that there exists a3 and a4 in A \ U such that a3 ∈ NG (b2 ),
a3 6∈ NG (b1 ), a4 ∈ NG (b1 ), and a4 6∈ NG (b2 ). This case is the most involved one,
as many subcases have to be considered. Namely, we need to take care that there
is no vertex in B \ U 0 of degree 0 in G − U 0 and to make sure that property (h) is
maintained. In order to reduce the number of subcases, we sometimes do not take
into consideration some vertex u of B that became of degree 0 in G − U after the
update of U 0 in the cases where property (g) is still maintained with the value
of s00 , f 00 , and d00 such that d00 = d0 − 2 and f 00 = f 0 + 2. This excludes the case
where u is connected to {v1 , v2 , v3 } such that γ 0 (vi ) =` for every i ∈ [3] and then
we can safely define U 00 = U 0 ∪ {u}, M 00 = M 0 ∪ {{u, v1 }}, and γ 00 (v) = γ 0 (v) for
every v ∈ (A ∩ U 0 ) \ {v1 , v2 , v3 }, γ 00 (v1 ) = >, and γ 00 (v2 ) = γ 00 (v3 ) = ⊥. The same
applies to the case where u is connected to {v1 , v2 , v3 } such that there exists
i ∈ [3] such that γ 0 (vi ) 6=`. In this case, we only add u to U 0 without adding
edges to M 0 , but for every i ∈ [3] such that γ 0 (vi ) =`, then γ 0 (vi ) = ⊥. This last
condition is necessary in order to make sure that property (d) is maintained. In
both cases, we will ignore these vertices of B in the analysis, but we need to keep
in mind that we need to add them each time one of these cases appears. We also
sometime forget the third neighbor of a vertex of A whenever its existence does
not change how to resolve the pattern.
Let K = {a1 , a2 , a3 , a4 , b1 , b2 }. As there are at most five edges between K and
V (G) \ (U ∪ K), at most two vertices of B can become of degree 0. We depict in
Fig. 5 every possible way these vertices can be connected to K together with the
possible extra edge from K to V (G) \ (U ∪ K). First note that Patterns (ii), (iii),
and (x) have no neighbor outside of the pattern and contain less than 10 vertices,
so we have already resolved these patterns. Note also that Patterns (iv), (v), (vi),
and (ix) correspond to patterns of condition (1) and so are not in G. Moreover,
Patterns (xi), (xii), and (xiii) do not need to have vertices labeled ` in order to
define the triple (U 0 , M 0 , γ 0 ) that incorporates the corresponding pattern to the
part already treated and that respects properties (a) to (h). Therefore, there are
only three remaining patterns to resolve, namely (i), (vii), and (viii). Note that
in these three cases, there is at most one extra vertex of B.
In the following, we focus our attention on Pattern (i) but the same arguments
apply to Patterns (vii) and (viii). As discussed above, we need to take care of
property (h). If the pattern has no neighbor inside a C4 , then we can extend the
triple (U, M, γ) where the vertices of A of this pattern that will not be labeled
> are labeled `. Note that in this case, properties (a) to (h) are maintained.
Assume that there is a C4 such that exactly one vertex of this C4 is a neighbor
of a vertex of K. Then we are in on of the cases depicted in Fig. 6, and we can
extend the triple (U, M, γ). Assume now that it is not the case and there is a
C4 with two vertices of this C4 that have a neighbor in K. Then we are in one
of the cases depicted in Fig. 7. For Pattern (xviii), it cannot exist because of
condition (1). For Pattern (xvi), we can extend the triple (U, M, γ) according to
the figure. For Pattern (xvii), we assume that for both C4 ’s of this pattern, we
cannot have either Pattern (xvi) or any of the patterns of Fig 6. Otherwise, we
start by solving one of these patterns. This implies that we can extend the triple
(U, M, γ) where the vertices of A of the pattern that will not be labeled > are
labeled `, and still respect property (h).

Uniquely restricted matchings and edge colorings

13

Fig. 6. Fourth case of C41 .

Pattern (xvi).

Pattern (xvii).

Pattern (xviii).

Fig. 7. Fifth case of C41 .

Case 3: there exists a C42 G0 in G \ U .
We assume in this case that for every u ∈ B \ U , dŪ (u) ≥ 1 and there is no C41
in G − U . In particular, this implies that Case 2 will not occur anymore, and
therefore, in the following property (h) will always be maintained. Thus, now we
only focus on properties (a) to (g). Let V (G0 ) ∩ A = {a1 , a2 } and V (G0 ) ∩ B =
{b1 , b2 }. For this case, when we say that we define M 0 and γ 0 by updating the
values of M and γ according to a figure, it means that we add to M every red edge
of the figure and for every v of A that is depicted in the figure, then γ 0 (v) = > if
v is either the endpoint of a red edge or v ∈ U and γ(v) = >, otherwise either v
has a neighbor outside of the pattern depicted in the figure, and thus γ 0 (v) =`,
or it does not and thus γ 0 (v) = ⊥.
First, assume that NG (b1 ) = NG (b2 ) = {a1 , a2 }. In this case, we need to
distinguish between the labels of the vertices of (NG (b1 ) ∪ NG (b2 )) ∩ U . There
are four possibilities depicted in Fig. 8. We define U 0 to be the union of U and

14

Julien Baste, Dieter Rautenbach, and Ignasi Sau

>

>

>

`

`

`

`

U
V (G) \ U

(i) Connected

(ii) Connected

(iii) Connected

(iv) Both connected

to > and >.

to > and `.

to ` and `.

to the same `.

Fig. 8. First cases of C42 . The vertices of A ∩ U labeled ⊥ are treated in the same
way than vertices labeled `. If both are connected to the same vertex labeled >,
the case depicted in subfigure (i) applies.
the vertices of G0 , and we define M 0 and γ 0 by updating the values of M and γ
according to Fig. 8. One can check that, in each case, properties (a) to (g) are
maintained.
Secondly, assume that there exists a3 ∈ A \ U such that a3 ∈ NG (b2 ) and
a3 6∈ NG (b1 ). Then we are in the case depicted in Fig. 9. We define U 0 to be
the union of U and the vertices of G0 , and we define M 0 and γ 0 by updating the
values of M and γ according to Fig. 9. One can check that properties (a) to (g)
are maintained.

Fig. 9. Second case of C42 .
Thirdly, assume that there exist a3 and a4 in A \ U such that a3 ∈ NG (b2 ),
a3 6∈ NG (b1 ), a4 ∈ NG (b1 ), and a4 6∈ NG (b2 ). As in Case 2, this situation is a bit
more complicated to handle, but now we do not need to take care of property (h),
which simplifies the case analysis compared to Case 2. Again, we shall ignore the
vertices of B that became of degree 0 after the removal of the new U 0 when the
situation is favorable to us, i.e., in exactly the same situations as in Case 2, and
thus it does not interfere with the fact that the new triple (U 0 , M 0 , γ 0 ) respects
property (g). We also sometimes forget the third neighbor of a vertex of A when
its existence does not change how to resolve the pattern. Using the fact that, by
condition (2), two vertices cannot have the same neighborhood, it follows that the
possible patterns are those depicted in Fig. 10. As Pattern (ii) is not connected to
the rest of the graph and has less than 10 neighbors, it has already been treated
by the algorithm. Note that Pattern (iii) cannot exist because of condition (1).
For all other patterns, namely Pattern (i) and Patterns (iv) to (ix), we define U 0
to be the union of U and the vertices of the given pattern, and we define M 0 and
γ 0 by updating the values of M and γ according to Fig. 9. One can check that
properties (a) to (g) are maintained.

Uniquely restricted matchings and edge colorings

Pattern (i).

Pattern (ii).

Pattern (iii).

Pattern (v).

Pattern (vi).

Pattern (iv).

Pattern (vii).

Pattern (viii).

Pattern (ix).

15

Fig. 10. Third case of C42 .

Case 4: there exists u ∈ B \ U such that dŪ (u) = 2.
We assume in this case that for every u ∈ B \ U , dŪ (u) ≥ 2, and that there is no
C4 in G − U .
Let u ∈ B \ U such that dŪ (u) = 2. Let {v1 , v2 } = NG (u) \ U and W =
NG (u) ∩ U , and U 0 = U ∪ {u, v1 , v2 }. Note that both v1 and v2 have at least one
neighbor that is not in U . Note also that |W | ≤ 1.
Assume first that W = ∅ or W = {w} and γ(w) 6=`. Let M 0 arise from
M by adding the edge uv1 . Let γ 0 be obtained from γ where γ 0 (v1 ) = > and
γ 0 (v2 ) =`. Clearly, replacing (U, M, γ) with (U 0 , M 0 , γ 0 ), properties (a) to (f) are
maintained. We obtain that s0 = s + 1, d0 = d + 1, and f 0 = f . These inequalities
directly imply that property (g) is maintained.
Assume now that W = {w} and γ(w) =`. Let M 0 arise from M by adding
the edge uw. Let γ 0 be obtained from γ where γ 0 (v1 ) = γ 0 (v2 ) =` and γ 0 (w) = >.
Clearly, replacing (U, M, γ) with (U 0 , M 0 , γ 0 ), properties (a) to (f) are maintained.
We obtain anew that s0 = s + 1, d0 = d + 1, and f 0 = f . These inequalities imply
again that property (g) is maintained.

16

Julien Baste, Dieter Rautenbach, and Ignasi Sau

Since the considered cases exhaust all possibilities, and in each case we described
an extension that maintains the relevant properties, the proof is complete up
to the running time of the algorithm, which we proceed to analyze. One can
easily check whether an extension operation can be realized in time O(n), where
n = n(G). Indeed, we consider a constant number of patterns, and in each of
them we fix a specific vertex. Then, for each vertex in V (G) \ U , we can check
whether this vertex corresponds to a specific vertex of one of the patterns in
constant time, by exploring the neighborhood at distance at most p − 1 from
this vertex, where p = 11 is the size of the largest pattern (cf. Fig. 6). As in each
extension operation the size of U is incremented by at least one, it follows that
the overall running time of the algorithm is O(n2 ).
2
Equipped with Lemma 2, we are now ready to prove Theorem 2.
Proof of Theorem 2: Again, we give an algorithmic proof such that the running
time of the corresponding algorithm is polynomial in n(G). Let α = 95 and let
G be the set of all bipartite graphs G of maximum degree at most 3 such that
every component of G has a vertex of degree at most 2. First, we prove that, for
every given graph G in G, one can find in polynomial time a uniquely restricted
matching M of size at least ανur (G). Therefore, let G be in G.
In order to be able to apply Lemma 2, we apply some reductions. Namely,
as long as at least one of the following conditions is fulfilled in G, we apply the
corresponding reduction, which is described and analyzed below:
• Condition (1): G contains one of the patterns R.1, R.2, R.3, R.4, R.5, or R.6
depicted in Fig. 2.
• Condition (2): There exist two vertices in G with the same neighborhood.
• Condition (3): There exists a vertex u in G of degree 1.
• Condition (4): There exists a vertex u in G of degree 0.
Reduction (1). First, if there is in G a subgraph P isomorphic to the pattern R.1
or the pattern R.2 depicted in Fig. 2(i) and Fig. 2(ii), respectively, such that only
the vertex x has a neighbor outside of P in G, then we define G0 to be the graph
obtained from G by removing every vertex of P except vertex x as depicted in
Fig. 2(i) and Fig. 2(ii). Then, if there is in G a subgraph P isomorphic to the
pattern R.3 or the pattern R.4 depicted in Fig. 2(iii) and Fig. 2(iv), respectively,
such that only the vertices x and y have a neighbor outside of P in G, then we
define G0 to be the graph obtained from G by removing every vertex of P except
vertices x and y as depicted in Fig. 2(iii) ad Fig. 2(iv). Finally, if there is in
G a subgraph P isomorphic to the pattern R.5 or the pattern R.6 depicted in
Fig. 2(v) and Fig. 2(vi), respectively, such that only the vertices x, y, and z have
a neighbor outside of P in G, then we define G0 to be the graph obtained from G
by removing every vertex of P except vertices x, y, and z as depicted in Fig. 2(v)
and Fig. 2(vi).
Let M ∗ be the set of red edges depicted in the corresponding figures. Then
νur (G0 ) ≥ νur (G) − |M ∗ |. Indeed, in each case, we can exhaustively check that
we cannot select more edges inside the pattern P , and in each configuration we
provide, in the figures, a solution that leaves vertex x (and vertices y and z,
if they exist) free to be taken from outside of P . Moreover, the choice of the
red edges is such that they cannot be inside any alternating cycle, whatever the

Uniquely restricted matchings and edge colorings

17

edges we select outside of P . If M 0 is a uniquely restricted matching of G0 , then
M 0 ∪ M ∗ is a uniquely restricted matching of G.
Reduction (2). Assume that v and v 0 are two vertices having exactly the same
neighborhood in G. We define G0 = G−{v 0 }. Indeed, v and v 0 cannot be inside the
same uniquely restricted matching, as otherwise there would exist an alternating
cycle. This implies that νur (G0 ) ≥ νur (G). Hence, we can safely remove v 0 from
G. If M 0 is a uniquely restricted matching of G0 , then M 0 is a uniquely restricted
matching of G.
Reduction (3). If G has a vertex u of degree 1, and v is the neighbor of u, then let
G0 = G − {u, v}. Clearly, νur (G0 ) ≥ νur (G) − 1, and if M 0 is a uniquely restricted
matching of G0 , then M 0 ∪ {uv} is a uniquely restricted matching of G.
Reduction (4). If G has a vertex u of degree 0, then let G0 = G − {u}. Clearly,
νur (G0 ) = νur (G), and if M 0 is a uniquely restricted matching of G0 , then M 0 is
a uniquely restricted matching of G.
In each of the four reductions defined above, note that the graph G0 belongs
to G. Similarly to in the proof of Lemma 2, it can be checked whether a reduction
can be realized in time O(n), where n = n(G).
By iteratively repeating these reductions, we eventually obtain a set M1 of edges
of G as well as a subgraph G2 of G such that G2 ∈ G, G2 does not contain a
subgraph P isomorphic to one of the patterns R.1, R.2, R.3, R.4, R.5, or R.6
depicted in Fig. 2, G2 does not contain two vertices with the same neighborhood,
νur (G2 ) ≥ νur (G)−|M1 |, M1 ∪M2 is a uniquely restricted matching of G for every
uniquely restricted matching M2 of G2 , and either n(G2 ) = 0 or δ(G2 ) ≥ 2. Now,
by suitably choosing the bipartition of each component K of G2 , and applying
Lemma 2 to K, one can determine in polynomial time a uniquely restricted
matching M2 of G2 with |M2 | ≥ ανur (G2 ). Since the set M1 ∪ M2 is a uniquely
restricted matching of G of size at least |M1 | + ανur (G2 ) ≥ |M1 | + α(νur (G) −
|M1 |) ≥ ανur (G), the proof of our claim about G is complete. Note that the overall
running time of the algorithm for graphs in G is O(n2 ), since each reduction
strictly decreases the size of the graph, and the algorithm of Lemma 2 also runs
in time O(n2 ).
Now, let G be a given connected bipartite graph G of maximum degree at
most 3. If G is not 3-regular, then G ∈ G, and the desired statement already
follows. Hence, we may assume that G is 3-regular, which implies that its two
partite sets A and B are of the same order. By [29], we can efficiently decide
whether νur (G) = ν(G). Furthermore, if νur (G) = ν(G), then, again by [29],
we can efficiently determine a maximum matching that is uniquely restricted.
Hence, we may assume that νur (G) < ν(G). This implies that νur (G) < |A|,
and, hence, there is some vertex u in V (G) such that νur (G − u) = νur (G). Since
G − u ∈ G for every vertex u of G, considering the n(G) induced subgraphs
G − u for u ∈ V (G), one can determine in polynomial time a uniquely restricted
matching M of G with |M | ≥ max{ανur (G − u) : u ∈ V (G)} = ανur (G). Thus,
we obtain an algorithm that finds the desired uniquely restricted matching. Note
that since we make O(n) to the algorithm for graphs in G, the overall running
time is O(n3 ).
2

18

4

Julien Baste, Dieter Rautenbach, and Ignasi Sau

Upper bounds on χ0ur (G)

Our first result in this section applies to general graphs, and its proof relies
on a natural greedy strategy. Faudree, Schelp, Gyárfás, and Tuza conjectured
χ0s (G) ≤ ∆2 for a bipartite graph G of maximum degree ∆, and our Theorem 3
can be considered a weak version of this conjecture. Theorem 4 below shows that
excluding the unique extremal graph from Theorem 3, the uniquely restricted
chromatic index of bipartite graphs drops considerably.
Theorem 3. If G is a connected graph of maximum degree at most ∆, then
χ0ur (G) ≤ ∆2 with equality if and only if G is K∆,∆ .
Proof: Since no two edges of K∆,∆ form a uniquely restricted matching in this
graph, we obtain χ0ur (K∆,∆ ) = |E(K∆,∆ )| = ∆2 . Now, let G be a connected
graph of maximum degree at most ∆. We first show that χ0ur (G) ≤ ∆2 . In a
second step, we show that χ0ur (G) < ∆2 provided that G is not K∆,∆ .
We consider the vertices of G in some linear order, say u1 , . . . , un . For i from
1 up to n, we assume that the edges of G incident with vertices in {u1 , . . . , ui−1 }
have already been colored, and we color all edges between ui and {ui+1 , . . . , un }
using distinct colors, and avoiding any color that has already been used on a
previously colored edge incident with some neighbor of ui . Since ui has at most
∆ neighbors, each of which is incident with at most ∆ edges, this procedure
requires at most ∆2 many distinct colors.
Suppose, for a contradiction, that some color class M is not a uniquely restricted matching in G. Since M is a matching by construction, there is an
M -alternating cycle C. Let C : ur1 us1 ur2 us2 . . . urk usk ur1 be such that r1 is the
minimum index of any vertex on C, and ur1 usk ∈ M . These choices trivially
imply r1 < s1 and r1 < r2 . If r2 > s1 , then ur1 usk ∈ M implies that, when
coloring the edge us1 ur2 , some edge incident with the neighbor ur1 of us1 would
already have been assigned the color of the edges in M , and the above procedure would have avoided this color on us1 ur2 . Therefore, since ur1 usk ∈ M and
ur2 us1 ∈ M , the coloring rules imply r2 < s1 , that is, r1 < r2 < s1 . Now, suppose
that ri < ri+1 < si for some i ∈ [k − 1]. Since uri+1 usi ∈ M and uri+2 usi+1 ∈ M ,
the coloring rules imply in turn
• ri+1 < si+1 , since otherwise we would have colored uri+1 usi differently,
• ri+2 < si+1 , since otherwise we would have colored uri+2 usi+1 differently, and
• ri+1 < ri+2 , since otherwise we would have colored uri+1 usi differently.
It follows that ri+1 < ri+2 < si+1 , where we identify rk+1 with r1 . Now, by an
inductive argument, we obtain r1 < r2 < · · · < rk < r1 , which is a contradiction.
Altogether, we obtain χ0ur (G) ≤ ∆2 .
Now, let G be distinct from K∆,∆ , and we want to prove that χ0ur (G) < ∆2 .
Among all uniquely restricted edge colorings of G using colors in [∆2 ], we choose
a coloring for which the number of edges with color 1 is as small as possible.
Clearly, we may assume that some edge uv has color 1, as otherwise we already
have that χ0ur (G) < ∆2 .
If there is a color α in [∆2 ] \ {1} such that no edge incident with a neighbor
of u has color α, then changing the color of uv to α yields a uniquely restricted
edge coloring of G with less edges of color 1, which is a contradiction. In view

Uniquely restricted matchings and edge colorings

19

of the maximum degree, this implies that every vertex in NG [u] has degree ∆,
the set NG (u) is independent, and, for every color α in [∆2 ], there is exactly one
edge incident with a neighbor of u that has color α.
Since G is not K∆,∆ , some neighbor x of u has a neighbor y that does not lie
in NG (v). Without loss of generality, let ux have color 2, and let xy have color
3. Let M be the set of edges with color 3.
If G does not contain an M -alternating path of odd length at least 3 between
x and a vertex in NG (v) \ {u} that contains the edge xy, then changing the color
of uv to 3 yields a uniquely restricted edge coloring of G with less edges of color
1, which is a contradiction. Hence, G contains such a path, which implies that
two edges incident with neighbors of y have color 3.
If there is a color α in [∆2 ] \ {1} such that no edge incident with a neighbor
of y has color α, then changing the color of xy to α and the color of uv to 3
yields a uniquely restricted edge coloring of G with less edges of color 1, which
is a contradiction. Similarly as above, this implies that, for every color α in
[∆2 ] \ {1, 3}, there is exactly one edge incident with a neighbor of y that has
color α. Now, changing the color of uv to 2, the color of ux to 3, and the color
of xy to 2 yields a uniquely restricted edge coloring of G with less edges of color
1, which is a contradiction. This completes the proof.
2
As observed above, the proof of Theorem 3 is algorithmic; the simple greedy
strategy considered in its first half efficiently constructs uniquely restricted edge
colorings using at most ∆2 colors. Furthermore, also its second half can be turned
into an efficient algorithm that finds uniquely restricted edge colorings using at
most ∆2 − 1 colors for connected graphs of maximum degree ∆ that are distinct
from K∆,∆ ; the different cases considered in the proof correspond to simple
manipulations of a given uniquely restricted edge coloring that iteratively reduce
the number of edges of color 1 down to 0. Golumbic, Hirst, and Lewenstein [14]
showed that deciding whether a given matching is uniquely restricted can be
done in polynomial time, and their algorithm can be used to decide which of the
simple manipulations can be executed.
Our next goal is to improve Theorem 3 for bipartite graphs. The following
proof was inspired by Lovász’s [24] elegant proof of Brooks’ Theorem.
Lemma 3. If G is a connected bipartite graph of maximum degree at most ∆ ≥ 4
that is distinct from K∆,∆ , and M is a matching in G, then M can be partitioned
into at most ∆ − 1 uniquely restricted matchings in G.
Proof: Let A and B be the partite sets of G, and let R = V (G) \ V (M ). Note
that M is perfect if and only if R is empty. Whenever we consider a coloring
of the edges in M , and α is one of the colors, let Mα be the set of edges in M
colored with α.
First, we assume that R is empty, and that G is not ∆-regular. By symmetry,
we may assume that some vertex a in A has degree less than ∆. Let ab ∈ M . Let
T be a spanning tree of G that contains the edges in M . Contracting within T
the edges from M , rooting the resulting tree in the vertex corresponding to the
edge ab, and considering a breadth-first search order, we obtain the existence of
a linear order a1 b1 , . . . , an bn of the edges in M such that ab = an bn , and, for
every i ∈ [n − 1], there is an edge between {ai , bi } and {ai+1 , bi+1 , . . . , an , bn }.
Since an has degree less than ∆, this implies that, for every i ∈ [n], some vertex

20

Julien Baste, Dieter Rautenbach, and Ignasi Sau

ui in {ai , bi } has at most ∆ − 2 neighbors in {a1 , b1 , . . . , ai−1 , bi−1 }. Now, we
color the edges in M greedily in the above linear order. Specifically, for every i
from 1 up to n, we color the edge ai bi with some color α in [∆ − 1] such that,
for every j ∈ [i − 1], for which ui has a neighbor in {aj , bj }, the edge aj bj is not
colored with α. By the degree condition on ui , such a coloring exists. Suppose,
for a contradiction, that Mα is not uniquely restricted for some color α in [∆−1].
Let the edge ai bi in Mα be such that it belongs to some Mα -alternating cycle C,
and, subject to this condition, the index i is maximum. If the neighbor of ui on
C outside of {ai , bi } is in {aj , bj }, then the choice of the edge ai bi implies j < i,
and the coloring rule implies that the edge aj bj is not colored with α, which is a
contradiction. Altogether, the statement follows.
Next, we assume that R is non-empty. Let K be a component of G − R. Let
MK be the set of edges in M that lie in K. Since G is connected, the graph K
is not ∆-regular. Therefore, proceeding exactly as above, we obtain a coloring of
the edges in MK using the colors in [∆−1] such that each color class is a uniquely
restricted matching in K. If K1 , . . . , Kk are the components of G − R, and Mi
is a uniquely restricted matching in Ki for every i ∈ [k], then M1 ∪ · · · ∪ Mk is
a uniquely restricted matching in G. Therefore, combining the colorings within
the different components, we obtain that also in this case the statement follows.
At this point, we may assume that G is ∆-regular, and that M is perfect.
Next, we assume that there are two distinct edges e and e0 in M such that
V ({e, e0 }) is a vertex cut of G. This implies that we can partition the set M \{e, e0 }
into two non-empty sets M1 and M2 such that there is no edge between V (M1 )
and V (M2 ). For i ∈ [2], let Gi be the subgraph of G induced by V ({e, e0 } ∪ Mi ).
Since G is connected, the graph Gi is not ∆-regular. In view of the above, this
implies that there is a coloring ci of the edges of the perfect matching {e, e0 } ∪ Mi
of Gi using the colors in [∆ − 1] such that each color class of ci is a uniquely
restricted matching in Gi . If ci (e) 6= ci (e0 ) for both i in [2], then we may assume
that c1 and c2 assign the same colors to e and e0 , and it is easy to verify that the
common extension c of c1 and c2 to M has the property that every color class of
c is a uniquely restricted matching in G. Hence, we may assume that necessarily
c1 (e) = c1 (e0 ). Note that this implies in particular that at least one of the two
possible edges between V ({e}) and V ({e0 }) is missing.
Let c1 (e) = α. Let e = ab, e0 = a0 b0 , and U = {a, b, a0 , b0 }. For every vertex
u ∈ U , let C1 (u) be the set of colors β for which M1 contains an edge vw with
c1 (vw) = β such that u is adjacent to v or w. If there is some u ∈ U and
some color β ∈ ([∆ − 1] \ {α}) \ C1 (u), then changing the color of the unique
edge in {e, e0 } incident with u from α to β yields a coloring c01 of the edges in
{e, e0 }∪M1 using the colors in [∆−1] such that each color class of c01 is a uniquely
restricted matching in G1 . Furthermore, c01 (e) 6= c01 (e0 ), which is a contradiction.
This implies that [∆−1]\{α} ⊆ C1 (u) for every u ∈ U . In particular, each vertex
u in U has at least ∆ − 2 neighbors in V (M1 ), and, hence, at most one neighbor
in V (M2 ). Let C2 (u) for u ∈ U be defined analogously as above. Clearly, the set
C2 (a) ∪ C2 (a0 ) contains at most two distinct colors. Since ∆ − 1 ≥ 3, we may
assume that c2 is such that the set C2 (a) ∪ C2 (a0 ) does not contain the color α.
Now, let c02 be a coloring of the edges in {e, e0 } ∪ M2 that coincides with c2 on
M2 and colors e and e0 with color α. It is easy to see that each color class of c02
is a uniquely restricted matching in G2 . Let c be the common extension of c1
and c02 to M . Suppose, for a contradiction, that the color class Mβ of c is not

Uniquely restricted matchings and edge colorings

21

uniquely restricted for some color β in [∆ − 1]. Clearly, we have β = α. Let C
be an Mα -alternating cycle in G. It is easy to see that C contains both edges e
and e0 Furthermore, since at least one of the two possible edges between {a, b}
and {a0 , b0 } is missing, it follows that C contains an edge between {a, a0 } and
V (M2 ). Since c coincides with c2 on M2 , and C2 (a) ∪ C2 (a0 ) does not contain α,
we obtain a contradiction.
Altogether, we may assume that there are no two distinct edges e and e0 in
M such that V ({e, e0 }) is a vertex cut of G.
Now, we show the existence of three edges ab, a0 b0 , and a00 b00 in M such
that some of the two possible edges between {a0 , b0 } and {a00 , b00 } is missing,
and either a is adjacent to b0 as well as b00 or b is adjacent to a0 as well as a00 .
Therefore, let a1 b1 be an edge in M . Let a2 b2 , . . . , a∆ b∆ be the edges in M such
that NG (a1 ) = {b1 , . . . , b∆ }. We may assume that {a2 , b2 , . . . , a∆ , b∆ } induces a
complete bipartite graph K∆−1,∆−1 ; otherwise, we find the three edges with the
desired properties. Since G is not K∆,∆ , the vertex b1 is non-adjacent to some
vertex ai in {a2 , . . . , a∆ }. Now, if aj ∈ {a2 , . . . , a∆ } \ {ai }, then one of the two
possible edges between {a1 , b1 } and {ai , bi } is missing, and bj is adjacent to a1
as well as ai . Altogether, we obtain three edges ab, a0 b0 , and a00 b00 in M with the
desired properties.
By symmetry, we may assume that a is adjacent to b0 and b00 , and a0 is
non-adjacent to b00 . In view of the above, the graph G0 = G − V ({a0 b0 , a00 b00 })
is connected, and M 0 = M \ {a0 b0 , a00 b00 } is a perfect matching of G0 . Let T 0
be a spanning tree of G0 that contains the edges in M 0 . Contracting within T 0
the edges from M 0 , rooting the resulting tree in the vertex corresponding to the
edge ab, and considering a breadth-first search order, we obtain the existence of a
linear order a3 b3 , . . . , an bn of the edges in M 0 such that ab = an bn , and, for every
i ∈ [n−1]\[2], there is an edge between {ai , bi } and {ai+1 , bi+1 , . . . , an , bn }. Now,
we color the edges in M greedily in the linear order a1 b1 , a2 b2 , a3 b3 , . . . , an bn ,
where a1 b1 = a00 b00 and a2 b2 = a0 b0 . Note that, for every i ∈ [n − 1] \ [2], some
vertex ui in {ai , bi } has at most ∆ − 2 neighbors in {a1 , b1 , . . . , ai−1 , bi−1 }. We
color a1 b1 and a2 b2 with the same color. For every i from 3 up to n − 1, we color
the edge ai bi with a color α in [∆ − 1] such that, for every j ∈ [i − 1], for which
ui has a neighbor in {aj , bj }, the edge aj bj is not colored with α. By the degree
condition on ui , such a coloring exists. Finally, since an has neighbors in the two
edges a1 b1 and a2 b2 that are colored with the same color, there is some color α
in [∆ − 1] for which no edge ai bi with i ∈ [n − 1] such that an is adjacent to bi ,
is colored with α, and we color the edge an bn with that color α. Suppose, for
a contradiction, that Mβ is not uniquely restricted for some color β in [∆ − 1].
Let the edge ai bi in Mβ be such that it belongs to some Mβ -alternating cycle C,
and, subject to this condition, the index i is maximum. Since a0 is non-adjacent
to b00 , we have i ≥ 3. Let un = an . If the neighbor of ui on C outside of {ai , bi }
is in {aj , bj }, then the choice of the edge ai bi implies j < i, and the coloring rule
implies that the edge aj bj is not colored with β, which is a contradiction. This
completes the proof.
2
Lemma 3 fails for ∆ = 3; the matching {a1 b1 , a2 b2 , a3 b3 , a4 b4 , a5 b5 } of the
graph G in Fig. 11 cannot be partitioned into two uniquely restricted matchings.
Note that the matching {a1 b3 , a2 b1 , a3 b5 , a4 b2 , a5 b4 } though is the union of the
two uniquely restricted matchings {a1 b3 , a3 b5 } and {a2 b1 , a4 b2 , a5 b4 }.

22

Julien Baste, Dieter Rautenbach, and Ignasi Sau

b1

b2

b3

b4

b5

s
s
s
s
s
H
HH HHHH@ 
@
H H 
@ H
H H
H@
HH H

H


@
H@
H
 @
H
@
Hs
Hs
s
s H
s H
a1

a2

a3

a4

a5

Fig. 11. A bipartite graph G.
Lemma 3 also fails for non-bipartite graphs; in fact, if G arises from the disjoint
union of two copies of K∆ by adding a perfect matching M , then every partition
of M into uniquely restricted matchings requires ∆ sets.
With Lemma 3 at hand, the proof of our final result is easy.
Theorem 4. If G is a connected bipartite graph of maximum degree at most
∆ ≥ 4 that is distinct from K∆,∆ , then χ0ur (G) ≤ ∆2 − ∆.
Proof: Since G is bipartite, its edge set can be partitioned into ∆ matchings [25].
By Lemma 3, each of these matchings can be partitioned into ∆ − 1 uniquely
restricted matchings. This completes the proof.
2
Note that the graph G in Fig. 11 also satisfies χ0ur (G) ≤ ∆2 − ∆ = 9 − 3 = 6.
In fact, the uniquely restricted matchings {a1 b1 , a4 b2 , a5 b4 }, {a1 b2 , a2 b4 , a5 b5 },
{a2 b1 , a3 b3 , a4 b5 }, {a1 b3 , a4 b4 }, {a2 b2 , a3 b5 }, and {a3 b1 , a5 b3 } partition E(G).

5

Concluding remarks

Our results motivate several open problems. As stated above, we believe that the
conclusion of Theorem 1 holds without the assumption of C4 -freeness. We also
believe that better approximation factors are possible, and that approximation
lower bounds in terms of the maximum degree could be proved. One could study
the approximability of the uniquely restricted matching number in other classes of
graphs. Finally, complexity results concerning the uniquely restricted chromatic
index should be provided.

References
1. N. Alon, B. Sudakov, and A. Zaks. Acyclic edge colorings of graphs. Journal of
Graph Theory, 37:157–167, 2001.
2. L. Andersen. The strong chromatic index of a cubic graph is at most 10. Discrete
Mathematics, 108:231–252, 1992.
3. A. Brandstädt and R. Mosca. On distance-3 matchings and induced matchings.
Discrete Applied Mathematics, 159:509–520, 2011.
4. H. Bruhn and F. Joos. A stronger bound for the strong chromatic index. arXiv,
1504.02583, 2015.
5. X. Cai, G. Perarnau, B. Reed, and A. Watts. Acyclic edge colourings of graphs
with large girth. arXiv, 1411.3047, 2014.
6. K. Cameron. Induced matchings. Discrete Applied Mathematics, 24:97–102, 1989.
7. K. Cameron. Induced matchings in intersection graphs. Discrete Mathematics,
278:1–9, 2004.

Uniquely restricted matchings and edge colorings

23

8. R. Diestel. Graph Theory. Graduate Texts in Mathematics, 2005.
9. L. Esperet and A. Parreau. Acyclic edge-coloring using entropy compression. European Journal of Combinatorics, 34:1019–1027, 2013.
10. R. Faudree, A. Gyárfás, R. Schelp, and Z. Tuza. Induced matchings in bipartite
graphs. Discrete Mathematics, 78:83–87, 1989.
11. R. Faudree, R. Schelp, A. Gyárfás, and Z. Tuza. The strong chromatic index of
graphs. Ars Combinatoria, 29B:205–211, 1990.
12. J. Fiamčik. The acyclic chromatic class of a graph. Mathematica Slovaca, 28:139–
145, 1978.
13. M. C. Francis, D. Jacob, and S. Jana. Uniquely restricted matchings in interval
graphs. arXiv, 1604.07016, 2016.
14. M. Golumbic, T. Hirst, and M. Lewenstein. Uniquely restricted matchings. Algorithmica, 31:139–154, 2001.
15. M. Henning and D. Rautenbach. Induced matchings in subcubic graphs without
short cycles. Discrete Mathematics, 35-316:165–172, 2014.
16. H. Hocquard, M. Montassier, A. Raspaud, and P. Valicov. On strong edge-colouring
of subcubic graphs. Discrete Applied Mathematics, 161:2467–2479, 2013.
17. H. Hocquard, P. Ochem, and P. Valicov. Strong edge-colouring and induced matchings. Information Processing Letters, 113:836–843, 2013.
18. P. Horák, H. Qing, and W. Trotter. Induced matchings in cubic graphs. Journal
of Graph Theory, 17:151–160, 1993.
19. F. Joos, D. Rautenbach, and T. Sasse. Induced matchings in subcubic graphs.
SIAM Journal on Discrete Mathematics, 28:468–473, 2014.
20. R. Kang, M. Mnich, and T. Müller. Induced matchings in subcubic planar graphs.
SIAM Journal on Discrete Mathematics, 26:1383–1411, 2012.
21. V. Levit and E. Mandrescu. Very well-covered graphs of girth at least four and local
maximum stable set greedoids. Discrete Mathematics, Algorithms and Applications,
3:245–252, 2011.
22. V. E. Levit and E. Mandrescu. Local maximum stable sets in bipartite graphs with
uniquely restricted maximum matchings. Discrete Applied Mathematics, 132:163–
174, 2003.
23. V. E. Levit and E. Mandrescu. Unicycle graphs and uniquely restricted maximum
matchings. Electronic Notes in Discrete Mathematics, 22:261–265, 2005.
24. L. Lovász. Three short proofs in graph theory. Journal of Combinatorial Theory,
Series B, 19:269–271, 1975.
25. L. Lovász and M. Plummer. Matching Theory. North-Holland, 1986.
26. V. Lozin. On maximum induced matchings in bipartite graphs. Information Processing Letters, 81:7–11, 2002.
27. S. Mishra. On the maximum uniquely restricted matching for bipartite graphs.
Electronic Notes in Discrete Mathematics, 37:345–350, 2011.
28. M. Molloy and B. Reed. A bound on the strong chromatic index of a graph. Journal
of Combinatorial Theory, Series B, 69:103–109, 1997.
29. L. Penso, D. Rautenbach, and U. Souza. Graphs in which some and every maximum
matching is uniquely restricted. arXiv, 1504.02250, 2015.
30. L. Stockmeyer and V. Vazirani. NP-completeness of some generalizations of the
maximum matching problem. Information Processing Letters, 15:14–19, 1982.
31. V. Vizing. On an estimate of the chromatic class of a p-graph. Diskretnyj Analiz,
3:25–30, 1964.
32. Q. R. Yu and G. Liu. Graph factors and matching extensions. Berlin: Springer;
Beijing: Higher Education Press, 2009.

