Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

Fast Distributed (∆ + 1)-Edge Coloring in Bipartite Graphs Yann Bourreau , Sebastian Brandt , and Ananth Narayanan CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

arXiv:2610.22690v1 [cs.DC] 15 Oct 2026

October 19, 2026 Abstract We show that, on bipartite n-vertex graphs in the LOCAL model of distributed computation, (∆ + 1)-edge coloring can be solved deterministically in O(f (∆) log n) rounds for some function f . In particular this implies a deterministic O(log n)-round upper bound for (∆ + 1)-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the5 e art bounds (which hold already on general graphs) whose n-dependencies are O(log n) rounds 2 e deterministically and O(log n) rounds randomized [Bernshteyn and Dhawan, J. Comb. Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of (∆ + 1)-edge coloring that corresponds to a local-palette strengthening of Vizing’s theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge {u, v} has to be colored with a color from {1, . . . , max(deg(u), deg(v)) + 1}. For all of our results, the vertices do not need to know on which side of the bipartition they lie—the structural promise of bipartiteness suffices.

1

Introduction

Edge coloring is one of the classical problems in graph theory, studied for many decades. One of the cornerstone results on edge coloring, Vizing’s theorem [49], states that every simple graph of maximum degree ∆ admits a proper edge coloring with ∆ + 1 colors, and this is best possible in general: odd cycles, for example, require three colors although ∆ = 2. Since Vizing’s discovery, (∆ + 1)-edge coloring has been examined across many models of computation, with substantial progress especially in recent years (see, e.g., [2–4, 11–15, 28, 29] for the most recent progress in sequential, dynamic, and distributed algorithms). In this work, we study the deterministic complexity of (∆ + 1)-edge coloring in the standard LOCAL model of distributed computation. The LOCAL model. In the LOCAL model [45], the input graph is considered as a communication network with the vertices (or nodes) of the graph representing computational entities: computation proceeds in synchronous rounds, and in each round every vertex may send an arbitrarily large message to each neighbor, receive the messages sent to it, and perform arbitrary local computation. Each vertex has to terminate at some point and then output its local part of the global solution to the considered problem; for (∆ + 1)-edge coloring, each vertex has to output a color from {1, . . . , ∆ + 1} for each of its incident edges such that endpoints of the same edge agree on the color of the edge. The runtime of a distributed algorithm governing the behavior of the vertices is simply the number of rounds until the last vertex has terminated. For a full definition of the LOCAL model, we refer the reader to Section 2. 1

When considering bipartite graphs in the LOCAL model, depending on the definition of the model in the bipartite setting, vertices may be aware on which side of the bipartition they lie or may not have this information. To distinguish between these two cases, we say that the vertices of a bipartite graph know (resp. do not know) the bipartition if each vertex is initially given one bit telling it on which side of a fixed bipartition it lies (resp. does not receive such information). Throughout the paper, n denotes the number of vertices of the input graph and ∆ denotes its maximum degree. Complexity bounds for (∆ + 1)-edge coloring. As recently as 2020, it was open whether Vizing’s theorem admits an implementation in the LOCAL model with runtime polylogarithmic in the global parameter n, even if an additional multiplicative dependence on the local parameter ∆ is allowed, i.e., whether (∆ + 1)-edge coloring can be solved in O(f (∆) logO(1) n) rounds for some function f . This question was answered in a breakthrough result by Bernshteyn who showed e (∆) log11 n) that (∆ + 1)-edge coloring admits a deterministic algorithm with a runtime of O(f e (∆) log6 n) rounds via multirounds1 [11]. Christiansen subsequently improved the bound to O(f step Vizing chains [28], and Bernshteyn and Dhawan improved it further to the current deterministic e (∆) log5 n) rounds [12]. In the same paper, Bernshteyn and Dhawan state-of-the-art bound of O(f also obtained the randomized state of the art by providing a randomized O(f (∆) log2 n)-round algorithm. On the lower bound side, it is known from [25] that, already on constant-degree graphs, Ω(log n) rounds are required for deterministic algorithms and Ω(log log n) rounds for randomized algorithms, leaving the question about the true complexity of (∆+1)-edge coloring wide open. In particular, the current state of deterministic upper and lower bounds raises the following fundamental question. Question 1. Can (∆ + 1)-edge coloring be solved deterministically in O(f (∆) log n) rounds, or is a superlogarithmic dependency on n necessary? An affirmative answer to Question 1 would also resolve an open question by Bernshteyn and Dhawan when restricted to bipartite graphs, asking whether there exists a deterministic or randomized O(log n)-round algorithm for (∆ + 1)-edge coloring on constant-degree graphs [12, Question 1.9]. Superlogarithmic lower bounds. Question 1 is also significant from the broader perspective of proving LOCAL lower bounds for locally checkable problems as we discuss next. Locally checkable labeling problems are problems that can be defined via local constraints—if around each vertex or edge the local constraints are satisfied by the output, the global solution is considered to be correct; otherwise it is considered to be incorrect. A large variety of problems that have been studied in the LOCAL model are locally checkable problems, including the central symmetry-breaking problems such as standard coloring problems, maximal independent set, or maximal matching. However, despite the ubiquity of locally checkable problems, the main general-purpose lower bound techniques for such problems, including round elimination [21, 23] and self-reduction [8, 42], the KMW lower bound framework [9, 44], and Marks’ technique [22, 47], are, in their present forms, inherently unable to prove deterministic lower bounds strictly above Ω(log n) rounds, except when the considered problem is already global (i.e., has an Ω(n)-round lower bound) on paths or cycles. We note that locally checkable problems exhibiting superlogarithmic lower bounds are known but, to the best of our knowledge, these are either highly artificial problems engineered specifically for the purpose of exhibiting a given complexity [7, 10, 27] or problems that require a high 1

e to hide a poly(log log n) factor. We also note that the exponent 11 was not given explicitly in [11] We use O(·) but observed later in [12].

2

polynomial number of rounds to be solved (such as global problems like 2-coloring a path, which √ require Ω(n) rounds, or locally optimal cut, which requires Ω( n) rounds [5]). In particular, there is no natural locally checkable problem that is known to be solvable in subpolynomial time but not in O(log n) rounds. An even stronger dichotomy appears when restricting attention to the class of problems on constant-degree graphs, which has been in the center of attention for many years (see, e.g., [7, 10, 26, 27, 36] for research on the distributed complexity landscape of so-called LCL problems, which are essentially locally checkable problems on constant-degree graphs): we are not aware of any natural locally checkable problem with a complexity known to liein both ω(log n) and o(n). Identifying a problem as described above is a major open question (which likely would require coming up with a broadly applicable new lower bound technique); even proving, say, an Ω(log n · log∗ n)-round lower bound for a natural non-global locally checkable problem on constant-degree graphs would be a major breakthrough. Due to its restrictive nature, (∆ + 1)-edge coloring is arguably one of the most promising candidates for such a superlogarithmic lower bound: after all, the task in the (∆ + 1)-edge coloring problem is to color with the existentially optimal number of colors, which is far below both the greedy threshold of 2∆ − 1 colors and the current state-ofthe-art number of colors known to admit a deterministic O(log n)-round edge coloring algorithm on constant-degree graphs, which is 3∆/2 [24]. In fact, even the arguably much less restrictive ∆vertex coloring problem, which allows only one color less than the greedily solvable (∆ + 1)-vertex coloring problem, was considered to be a candidate for exhibiting a superlogarithmic lower bound on constant-degree graphs (see [20, Section 1.1]) until a deterministic O(log n)-round algorithm was found recently [19].

1.1

Our Contributions

Our main contribution is the following theorem. Theorem 1.1. There exists a function f such that, on bipartite graphs, a (∆ + 1)-edge coloring can be computed deterministically in O(f (∆) log n) rounds. This holds even when the bipartition is not known to the vertices. Theorem 1.1 answers Question 1 affirmatively for bipartite graphs. It improves the previous e (∆) log5 n) rounds deterministic state of the art for (∆+1)-edge coloring on this graph class from O(f [12] to O(f (∆) log n) rounds, and it even improves over the previous randomized O(f (∆) log2 n)round bound [12] while remaining deterministic. In terms of the number of colors for which bipartite edge-coloring is known to be solvable in O(f (∆) log n) rounds, Theorem 1.1 improves over the previous state of the art of 3∆/2 colors [24]. We note that in all previous (∆ + 1)-edge coloring algorithms whose runtimes have a polylogarithmic dependency on n [11, 12, 29] the dependency on ∆ is polynomial, while in our algorithm the runtime is considerably superpolynomial. However, we also did not attempt to minimize the dependency on ∆, which is in line with the common2 focus on the dependency on n, leaving improving the exact dependency on the local parameter ∆ to future work. In particular, in light of the deterministic Ω(log n)-round lower bound proved in [25] we obtain the following important corollary of Theorem 1.1, which also answers an open question by Bernshteyn and Dhawan [12, Question 1.9] when restricted to bipartite graphs. 2

For instance, the previous state of the art by Bernshteyn and Dhawan [12] has a dependency of ∆84 and ∆36 on ∆ in the deterministic and randomized algorithms, respectively. In fact, the title of the paper “Fast algorithms for Vizing’s theorem on bounded degree graphs” already underlines the emphasis of current research on the n-dependency.

3

Corollary 1.2. On constant-degree bipartite graphs, with or without the bipartition being known to the vertices, the deterministic complexity of (∆ + 1)-edge coloring is Θ(log n) rounds. The tightness of our O(log n)-round upper bound on constant-degree bipartite graphs (which does not require that the vertices know the bipartition) follows from the fact that the aforementioned Ω(log n)-round lower bound holds already on constant-degree bipartite graphs where the bipartition is known to the vertices. From the general perspective of proving lower bounds, Theorem 1.1 and Corollary 1.2 show that (∆ + 1)-edge coloring, perhaps surprisingly, cannot be used for proving superlogarithmic lower bounds on constant-degree graphs, leaving open the question of finding another promising (non-artificial, non-global) candidate problem for exhibiting such a lower bound. Our results may also be surprising in the sense that bipartiteness is required only as a structural promise on the input instance: they show that, for (∆ + 1)-edge coloring, the existence of a bipartition can be algorithmically exploited without exposing that bipartition to the vertices. We see our results as a major step towards a full resolution of Question 1: solving the bipartite case is often a first step toward the general case (see, e.g., [1, 31, 38, 41, 46]), in particular in the context of matching problems, which play an essential role in our overall approach. Stronger local-palette statements. While Theorem 1.1 and Corollary 1.2 can be considered as our main results since they are stated for standard (∆ + 1)-edge coloring, we in fact prove stronger statements using a local color palette where the set of allowed colors for an edge is determined by the degrees of its endpoints (instead of by the global maximum degree). The relevant existential statement, shown in [29], is a local strengthening of Vizing’s theorem: every graph admits an edge coloring in which each edge {u, v} receives a color from the palette {1, . . . , max(deg(u), deg(v)) + 1}. We show that our algorithm can also be used to compute these more restrictive edge colorings, thereby obtaining the following two statements. Theorem 1.3. On bipartite graphs (even without the bipartition being known to the vertices), a (∆ + 1)-edge coloring where each edge {u, v} receives a color from {1, . . . , max(deg(u), deg(v)) + 1} can be computed deterministically in O(f (∆) log n) rounds, for some function f . Corollary 1.4. On constant-degree bipartite graphs (with or without the bipartition being known to the vertices), the deterministic complexity of (∆ + 1)-edge coloring where each edge {u, v} receives a color from {1, . . . , max(deg(u), deg(v)) + 1} is Θ(log n) rounds. We note that all polylogarithmic-in-n algorithms for (∆ + 1)-edge coloring [11, 12, 29] do not seem to extend to the local-palette version of Vizing’s theorem (in any known way): as such, Theorem 1.3 and Corollary 1.4 provide the first results for this problem with a polylogarithmic dependency on n.

1.2

Our Approach

In this section, we provide an informal high-level overview of our approach. For simplicity, we describe the algorithm for standard (∆ + 1)-edge coloring; the local-palette version can be obtained in a similar manner.

4

Comparison with prior work. Our algorithm follows a very different route from the Vizingchain-based approaches used in the previous algorithms for (∆ + 1)-edge coloring achieving a polylogarithmic dependency on n [11, 12, 29]. In those works, the edge coloring is constructed in iterations roughly as follows: In each iteration a subset S of uncolored edges is colored by finding, for each such edge e, a “chain” of edges, starting at e, that can be recolored in a way that guarantees that there exists a color c that no edge neighboring e is colored with. After recoloring the chain, e is then colored with color c. To avoid issues coming from interference between chains for different edges in S, the set S is selected so that these chains do not intersect, which requires a lot of care. In contrast, in our approach, we build the coloring one color class at a time: first we select a subset of edges that receive color ∆ + 1, then a subset of edges that receive color ∆, and so on. We guarantee that we color “sufficiently many” edges with each color so that after iterating through all colors no edge remains uncolored. In particular, once an edge receives a color, this edge will never be recolored later in the algorithm. Problematic vertices. If, in each iteration, we could find a perfect matching on the set of uncolored edges (and then assign the edges in this matching the currently considered color), this general approach would even yield a ∆-edge coloring. However, even with ∆+1 colors available, for high-degree vertices there is not much “slack” that we can exploit: for instance, if, for a vertex v of degree ∆, no incident edge is colored in some given iteration, then in all other iterations (exactly) one edge incident to v must be colored (as all ∆ incident edges must be colored at the end of the ∆ + 1 iterations and no two neighboring edges can be colored in the same iteration). To keep track of the vertices that already exhausted their slack throughout our algorithm, we essentially define a set of problematic vertices that grows across the ∆ + 1 iterations: as soon as, for a vertex v, the number of incident uncolored edges matches the number of remaining iterations for the first time, v becomes “problematic”, indicating that in every future iteration an incident edge has to be colored. Initially, no vertex is problematic as the number of remaining iterations is ∆ + 1. As, for an overall runtime of O(f (∆) log n) rounds, we may spend O(f (∆) log n) rounds in each of the ∆ + 1 iterations, we are left with the following challenge: in each iteration, compute a large matching in O(f (∆) log n) rounds that at the very least matches all problematic vertices (which defines a set of pairwise non-adjacent edges that then can be colored with a common color and guarantees that for each problematic vertex an incident edge is colored). Note that the larger the set of problematic vertices becomes, the closer to a perfect matching the matchings we compute in subsequent iterations have to become, which considerably complicates our task of finding such matchings fast. Keeping problematic vertices isolated. A key ingredient of our approach is to preserve the property that any two problematic vertices are far from each other. Perhaps surprisingly, we show that this can be guaranteed across essentially all iterations while paying only a logarithmic dependency on n in the runtime. More specifically, we maintain a lower bound on the minimum pairwise distance between problematic vertices that gracefully degrades across iterations; after the first iteration, problematic vertices are guaranteed to have a very large minimum pairwise distance and this distance guarantee decreases in each iteration. However, in each iteration, this lower bound on the pairwise distance of problematic vertices can be expressed purely as a function of ∆. In the following we explain how we compute a matching in a given iteration without decreasing the aforementioned guarantee on the minimum pairwise distance between problematic vertices too much. Consider some iteration i and assume that at the beginning of the iteration the problematic vertices are guaranteed to have a pairwise distance of at least d. Our task is to find a matching in

5

the graph induced by the uncolored edges that matches at least all problematic vertices but ideally many more (so that the number of problematic vertices increases as little as possible). Computing saturating matchings. To this end, one recent powerful technique that we would like to make use of is the deterministic “hypergraph sinkless orientation” algorithm from [24], which has already found a number of applications for different problems [19, 24, 39, 40, 48]. This algorithm is developed for bipartite graphs where the minimum degree a on one side of the bipartition (say, X) is strictly larger than the maximum degree b on the other side; it computes a matching that matches every vertex on side X (which we call an X-saturating matching). The runtime of the algorithm is O(loga/b n) rounds. Obstacles. Unfortunately, the graphs at the beginning of our iterations do not have the aforementioned properties required for the algorithm to work: while our graphs are bipartite, the vertices do not know on which side of the bipartition they lie, and the graphs do not satisfy the aforementioned max-min-degree relation in general. In fact, if our input graph is a ∆-regular (bipartite) graph (which, intuitively, is the worst possible instance as it provides the least slack in the aforementioned sense), the average degree on both sides of the bipartition is initially the same and will always remain the same as each edge that is “removed” due to becoming colored reduces the sum of degrees on both sides by 1. In that case, the graphs at the beginning of the iterations will be far away from anything satisfying the aforementioned max-min-degree relation. However, despite these issues that seem to rule out approaches using the algorithm from [24], we develop an approach that is at least partially inspired by that algorithm. Unsurprisingly, our approach requires a number of novel ingredients that need to be carefully combined. An extended algorithm for computing saturating matchings. One ingredient at the heart of our approach is an extension of the algorithm from [24] that works on all graphs satisfying a property that is much weaker than the aforementioned max-min-degree condition. Very informally, we show that even on bipartite graphs (X ∪ Y, E) where most vertices have the same degree (say, k), we can find an X-saturating matching fast if a certain set of vertices called good vertices lies sufficiently “denser” in the graph than a certain set of vertices called bad vertices (see Theorem 3.6). Here, the good vertices are simply the vertices in X with degree > k and the vertices in Y with degree < k whereas the bad vertices are the vertices in Y with degree > k.3 In a sense, the definitions of good and bad vertices resemble the discussed max-min-degree condition, though in a much weaker form. Given the impact that [24] had since its publication in 2025, we believe that our extension will be highly useful for developing even faster algorithms for various problems. The proof of the correctness and runtime of our extended algorithm is inspired by the proof for the algorithm in [24] but becomes substantially more involved due to the much weaker condition. Applying our algorithm on a virtual graph. While our new algorithm is applicable on a considerably larger class of graphs, the graphs at the beginning of the iterations still do not fall into this class in general, and we still have the issue that vertices are not aware of the bipartition underlying the input graphs. To solve the latter issue, we consider the bipartite double cover of the input graph, which we denote by B = (X ∪ Y, E) in the following. To solve the former issue, we “duplicate” a carefully chosen set of vertices of B and remove vertices in X with small degree, thereby changing the degrees of vertices of B in a way that guarantees that our new algorithm is 3

There is some asymmetry in the definition as for the graphs we will consider in this context, all vertices in X have degree ≥ k.

6

applicable on the obtained graph. The application of the algorithm then yields, in O(f (∆) log n) rounds, a matching that matches all (remaining) vertices in X. Unfortunately, the virtual graph on which we compute this matching is too different from the input graph to transform the computed matching directly into a matching on the input graph that satisfies the severe restrictions regarding size and problematic vertices required to sustain our approach over many iterations. However, we show that the computed matching is highly useful in a different manner: it gives rise to a wellstructured subgraph of the input graph which, in particular, satisfies strong degree guarantees, as detailed next. Extracting a well-structured subgraph of the input graph. Consider the set E ′ of edges e′ of our original input graph G for which at least one “copy” of e′ in B has been selected into the matching. Here, an edge e = {u, v} of B is considered as a copy of an edge e′ = {u′ , v ′ } of G if each of u and v is a copy of or duplicate of a copy of u or v in the bipartite double cover. We show that the edges in E ′ induce a subgraph G′ of G that has minimum degree 1 and maximum degree 3; moreover, if a vertex v has degree 3 in G′ , v is a vertex whose copy in B has been duplicated. We show further that the vertices to be duplicated can be selected (without compromising the applicability of our algorithm) in a way that guarantees that they are far away from each other and from the problematic vertices. Computing the desired matching. Finally, we find a matching M ′ on G′ (and therefore also on G) such that the vertices that remain unmatched are far away from each other and from problematic vertices (in G); we achieve this in O(f (∆) log n) rounds by exploiting the specific structure of G′ and combining it with a novel application of the sinkless orientation algorithm from [35]. The matching M ′ computed in this way now constitutes the set of edges that we color at the end of the current iteration (all with the same color reserved for this iteration). Since our construction of M ′ guarantees that the unmatched vertices are sufficiently far from each other and from problematic vertices (though the lower bound on the pairwise distance between these vertices is lower than the lower bound d at the start of the iteration), we obtain that the new set of problematic vertices at the start of the next iteration (which is a subset of the problematic vertices of the current iteration and the unmatched vertices) is again suitably lower bounded by some expression that is a function of ∆. Success across all iterations. Hence, by choosing our parameters carefully, we can guarantee that at the start of every iteration the lower bound guarantee on the minimum pairwise distance between problematic vertices suffices to perform the respective iteration in O(f (∆) log n) rounds, until the graph induced by the uncolored edges has maximum degree 3 and satisfies that vertices of degree 3 are still sufficiently far from each other. As, at this point, still 3 colors remain, it is easy to edge-color the remaining graph suitably by choosing different colors for any three edges incident to a common vertex of degree 3 and then fixing the coloring on the remaining paths and cycles in O(log∗ n) rounds. This completes the high-level description of our algorithm. Omitted details. We note that there are many intricate details of the algorithm and analysis that we omitted for simplicity. In particular, whenever at the start of an iteration the graph induced by the uncolored edges contains connected components of relatively small diameter, we solve these components simply by brute force, e.g., by collecting the entire component in one vertex, computing an edge coloring with the remaining colors on the component and distributing the solution to all vertices in the component. The existence of a proper edge coloring of the component with the 7

remaining colors follows from the fact that the number of remaining colors is at least as large as the maximum degree in the component and the well-known result that any bipartite graph is ∆-edge-colorable [43].

1.3

Further Related Work

Deterministic state-of-the-art bounds depending on the number of colors. The greedy threshold for edge coloring is 2∆ − 1: there is a sequential greedy algorithm with this number of colors that simply iterates through the edges in an arbitrary order and colors each edge with a color that none of its neighboring edges has been assigned. Due to its greedy nature, (2∆ − 1)edge coloring is often considered to be a considerably easier problem than (∆ + 1)-edge coloring; this view is supported by the current state-of-the-art runtimes for (2∆ − 1)-edge coloring, which are considerably below what is known (or even possible) for (∆ + 1)-edge coloring. In particular, 5/3 e (2∆ − 1)-edge coloring can be solved in O(log∗ n + log12 ∆) [6], O(log n log2 ∆) [34], and O(log n) rounds [33]. Due to a reduction proved in [40], the aforementioned upper bounds for (2∆ − 1)-edge coloring also apply to (2∆ − 2)-edge coloring, with the exception of the first bound, which instead degrades slightly to O(log log n + log12 ∆) rounds. On the lower bound side, however, there is a substantial difference between the two cases: for 2∆ − 1 colors nothing better than an Ω(log∗ n)-round lower bound is known [45] whereas the Ω(log n)-round lower bound discussed before applies as soon as the number of colors drops to 2∆ − 2 [25]. While no higher lower bound than Ω(log n) rounds is known down to (and including) ∆+1 colors, the state-of-the-art upper bounds become progressively worse with the number of colors decreasing. In particular, the best currently known bounds are e −2 log2 ∆ log n) rounds for ((3/2+ε)∆)-edge coloring (for any ε > 1/∆) [24], O(∆2 log n) rounds O(ε √ 2 e for (3∆/2)-edge coloring [24], and O(log2 n)+ O(log ∆ log n) rounds for ((1+ε)∆+O( log n))-edge coloring (for any constant ε > 0) [16]. Existential results for bipartite edge coloring. While our results use ∆ + 1-colors, it should be noted that existentially, every bipartite graph can be edge-colored with ∆ colors [43]; however, computing such a coloring in the LOCAL model takes Ω(n) rounds already on (even) cycles. In fact, as shown in [32], every bipartite graph can even be list-edge-colored with ∆ colors, i.e., if each edge is assigned a list of ∆ colors (from some arbitrary color space), then it is possible to select, for each edge, a color from its list such that the resulting coloring is proper. This result was strengthened in [17]: such a list edge coloring exists already if the list given to each edge {u, v} is of size max(deg(u), deg(v)), which shows that also for the local-palette version of Vizing’s theorem from [29] discussed before, the assumption of bipartiteness reduces the number of required colors by 1.

1.4

Open Problems

The most immediate open problem is to remove the bipartiteness assumption in Theorem 1.1 (or even Theorem 1.3), i.e., to fully answer Question 1. A second, orthogonal open problem is to reduce the dependency on ∆ as much as possible. A first goal could be to obtain a polynomial bound on ∆ (while still preserving the logarithmic dependency on n) but as currently no lower bound on the ∆-dependency is known if a logarithmic dependency on n is allowed, a perhaps even more important question is whether a clean O(log n)round algorithm (without any additional dependency on ∆) exists.

8

As already alluded to before, from the perspective of developing new lower bound techniques (or extending existing ones), a further important open problem is to identify natural (non-global) locally checkable problems that may exhibit superlogarithmic lower bounds already on constantdegree graphs (and prove such superlogarithmic lower bounds). Alternatively, it would be highly interesting to prove for wide classes of natural locally checkable problems exhibiting Ω(log n)-round lower bounds that these lower bounds are tight by proving matching upper bounds.

1.5

Roadmap

The remainder of the paper is split into three sections. In Section 2, we recall relevant definitions and results from the literature and introduce new concepts central to our approach. In Section 3, we develop our extended algorithm for computing saturating matchings. In Section 4, we present our edge coloring algorithm and prove Theorems 1.1 and 1.3.

2

Preliminaries

In this section we fix notation and collect the definitions and basic observations used throughout the paper. Graphs. For any graph G, let V (G) and E(G) denote the set of vertices and the set of edges of G, respectively. Let n denote the number of nodes of G and ∆ denote its maximum degree. For two graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ), let G1 ∪ G2 be the graph (V1 ∪ V2 , E1 ∪ E2 ). For any subset of edges E ′ ⊆ E(G), we denote by V (E ′ ) the set of nodes in the subgraph induced by the edges in E ′ . If E ′ = {e} for an edge e, we may simply denote it as V (e). Neighborhoods and distances. If x and y are neighbors in a graph G, we will call y a Gneighbor of x. We write the distance between nodes u and v in G by dG (u, v). For v ∈ V (G) we define NG (v) := {u ∈ V (G) | dG (u, v) = 1}, the open neighborhood of v. For v ∈ V (G) and integer t ≥ 0, let BG (v, t) := {u ∈ V (G) : dG (v, u) ≤ t} be the ball of radius t around v in G. Eccentricity and radius. For a graph G and node x ∈ V (G), the eccentricity of x in G, denoted eccG (x), is the maximum distance from x to any other node in G. The radius of G, denoted rad(G), is the minimum eccentricity among all vertices of G. Note that the eccentricity of any node in a connected graph G′ is at most twice rad(G′ ). The LOCAL model. In the LOCAL model of distributed computing [45], the input graph G = (V, E) is the same as the communication network. Each vertex v ∈ V is a processor that can perform arbitrarily large computation and has a unique O(log n)-bit identifier, where n := |V |. Initially, each vertex knows only its own identifier, its degree, and the identifiers of its neighbors (together with any problem-specific input on itself and its incident edges). Computation proceeds in synchronous rounds: in each round, every vertex sends a message of arbitrary size to each of its neighbors, receives the messages sent to it, and updates its local state. After a finite number of rounds, every vertex must terminate and irrevocably output its own part of the solution, where different vertices may terminate in different rounds; these local outputs must together constitute a valid global solution to the problem. For example, if the problem is to find a maximal independent set of the input graph, each vertex outputs whether or not it belongs to the set, and the vertices that declare membership must indeed form a maximal independent set. The round complexity (or 9

time complexity) of an algorithm is the number of rounds until all the vertices has terminated, in the worst case over all inputs (and identifier assignments). This model admits an equivalent formulation: a deterministic algorithm with round complexity T is precisely a function mapping the labeled radius-T neighborhood of a vertex to that vertex’s output, since in T rounds information can travel at most T hops, and conversely every vertex can collect its entire radius-T neighborhood in T rounds and then determine its output by local computation. An algorithm is randomized if each vertex additionally has access to a private source of random bits. Bipartite graphs. Let G = (X ⊔ Y, E) be a bipartite graph. If we want to distinguish between nodes in X and Y , we write G as the triple (X, Y, E); in this sense, (X, Y, E) and (Y, X, E) are considered different bipartite graphs. For a subgraph H = (X ′ , Y ′ , E ′ ) of G with X ′ ⊆ X and Y ′ ⊆ Y , we may denote X ′ and Y ′ as X(H) and Y (H) respectively. We may refer to nodes in X(H) as vertices on the X-side or simply X-vertices; the analogous convention applies to nodes in Y (H). For a bipartite graph G = (X, Y, E) and subsets X ′ ⊆ X, Y ′ ⊆ Y , we denote by G[X ′ , Y ′ ] the bipartite graph (X ′ , Y ′ , E ′ ) where E ′ is the set of edges of G between X ′ and Y ′ . A matching M in G is X-saturating if every node in X is an endpoint of an edge in M . Note that an X-saturating matching is a maximum matching in G. In the following, we formally introduce objects central to our overall approach (see Section 1.2). We start with a classification of vertices into good, bad, and neutral vertices. Definition 2.1. Let k ≥ 1 be an integer and let G = (X, Y, E) be a bipartite graph such that every x ∈ X has degG (x) ≥ k − 1 and every y ∈ Y has degG (y) ≤ k. We define the following terminology for the vertices of G. • A vertex u ∈ V (G) is k-good in G if either u ∈ X with degG (u) ≥ k, or u ∈ Y with degG (u) ≤ k − 2. Let Vgood (G, k) denote the set of k-good vertices in G. • A vertex u ∈ V (G) is k-bad in G if u ∈ Y and degG (u) = k. Let Vbad (G, k) denote the set of k-bad vertices in G. • A vertex u ∈ V (G) is k-neutral in G if degG (u) = k − 1. Let Vneutral (G, k) denote the set of k-neutral vertices in G. The degree assumption ensures that every vertex of G is either k-good, k-bad, or k-neutral in G. Next, we introduce the notion of a (k, α, β)-net, which will be central for our extended algorithm for computing a saturating matching. Informally, a (k, α, β)-net is a bipartite graph where degrees are tightly controlled and k-bad vertices are both rare and well-separated. The formal definition follows. Definition 2.2. Let k ≥ 1 be an integer, and let α, β be positive integers with β ≥ 2. A bipartite graph G = (X, Y, E) is a (k, α, β)-net if it satisfies the following three properties. 1. (Degree.) Every x ∈ X has degG (x) ≥ k − 1, and every y ∈ Y has degG (y) ≤ k. 2. (Reach.) For every y ∈ Y there exists u ∈ V (G) that is k-good in G with dG (y, u) ≤ α. 3. (Distance.) Any two distinct vertices y1 , y2 ∈ Y that are k-bad in G satisfy dG (y1 , y2 ) ≥ βα. The following weaker variant relaxes the reach property to apply only at k-bad vertices. 10

Definition 2.3. Let k ≥ 1 be an integer, and let α, β be positive integers with β ≥ 2. A bipartite graph G = (X, Y, E) is a weak (k, α, β)-net if it satisfies the following three properties. 1. (Degree.) Every x ∈ X has degG (x) ≥ k − 1, and every y ∈ Y has degG (y) ≤ k. 2. (Reach.) For every y ∈ Y that is k-bad in G, there exists u ∈ V (G) that is k-good in G with dG (y, u) ≤ α. 3. (Distance.) Any two distinct vertices y1 , y2 ∈ Y that are k-bad in G satisfy dG (y1 , y2 ) ≥ βα. These two notions are related in the obvious way. Observation 2.4. Every (k, α, β)-net is a weak (k, α, β)-net. Both of these notions also pass to connected components. Observation 2.5. Let G = (X, Y, E) be a bipartite graph and let C = (X ′ , Y ′ , E ′ ) be a connected component of G with X ′ ⊆ X, Y ′ ⊆ Y , and E ′ ⊆ E. If G is a (k, α, β)-net, then C is a (k, α, β)-net. If G is a weak (k, α, β)-net, then C is a weak (k, α, β)-net. Proof. Every vertex of C has all its neighbors in G inside C, so degC (v) = degG (v) for every v ∈ V (C) and dC (u, v) = dG (u, v) for every u, v ∈ V (C). In particular, a vertex of C is k-good, k-bad, or k-neutral in C exactly when it is so in G. Suppose G is a (k, α, β)-net. Then Property 1 for G directly gives Property 1 for C, and Property 3 for G directly gives Property 3 for C. For Property 2, given y ∈ Y ′ there exists u ∈ V (G) that is k-good in G with dG (y, u) ≤ α; since dG (y, u) is finite, u ∈ V (C), and u is k-good in C. The argument for the weak-net case is identical. We now focus on the notion of Hall graphs, a local object used in our matching construction. This notion was introduced in [24] in the setting of hypergraphs. We rephrase it to fit our setting. Definition 2.6. Let G = (X, Y, E) be a bipartite graph. Let H = (X ′ , Y ′ , E ′ ) be a subgraph of G where X ′ ⊆ X, Y ′ ⊆ Y and E ′ ⊆ E. We say that H is a Hall graph in G if • there exists an X ′ -saturating matching in H, and • NG (Y ′ ) ⊆ X ′ . For the rest of this section, we record some definitions and properties that are related to Hall graphs. All of these properties have appeared in equivalent forms in [24]. The next lemma is a straightforward consequence of Hall’s theorem: any bipartite graph G = (X, Y, E) with no isolated vertices and |X(G)| ≤ |Y (G)| contains a non-empty Hall graph. Lemma 2.7. Let G = (X, Y, E) be a bipartite graph with no isolated nodes such that |X| ≤ |Y |. Then there exists a non empty Hall graph H in G. Proof. We construct induced subgraphs G = G0 ⊇ G1 ⊇ · · · by repeatedly deleting specific nonempty set together with its neighborhood, halting once Hall’s condition holds. Set X0 := X, Y0 := Y , G0 := G. Given Gi = G[Xi , Yi ], halt and output H := Gi if |NGi (S)| ≥ |S| for every S ⊆ Xi ; otherwise fix S ⊆ Xi with |NGi (S)| < |S| and set Xi+1 := Xi \ S, Yi+1 := Yi \ NGi (S), Gi+1 := G[Xi+1 , Yi+1 ].

11

We claim that for every i for which Gi is defined, Yi = NGi (Xi ), NG (Yi ) ⊆ Xi .

(1) (2)

Both hold at i = 0, the former since G has no isolated nodes and the latter since all edges of G run between X and Y . Assume both at i and consider any y ∈ Yi+1 . Vertex y lies in Yi \ NGi (S), so by eq. (1) at i, it has a neighbor in Xi \ S = Xi+1 , giving eq. (1) at i + 1; and any x′ ∈ NG (y) lies in Xi by eq. (2) at i and not in S (else y ∈ NGi (S)), giving eq. (2) at i + 1. Induction on i now gives |Xi | ≤ |Yi |: at the inductive step, |Yi+1 | = |Yi | − |NGi (S)| ≥ |Yi | − |S| + 1 > |Xi |−|S| = |Xi+1 |. Hence S ⊊ Xi at every step, since S = Xi would give |NGi (Xi )| = |Yi | ≥ |Xi | by eq. (1), contradicting deficiency. So Xi+1 ̸= ∅ throughout, and as |Xi | strictly decreases the construction halts at some Gm with Xm ̸= ∅. By halting and Hall’s theorem [37], Gm admits an Xm -saturating matching; together with eq. (2), H := Gm is a non-empty Hall graph in G. The next definition formalizes what remains of a bipartite graph after a Hall graph is removed. Definition 2.8. Let G = (X, Y, E) be a bipartite graph and let H = (X ′ , Y ′ , E ′ ) be a (possibly empty) Hall graph in G. We define G \ H := G[ X \ X ′ , NG (X \ X ′ ) ]. More generally, given bipartite graphs H1 , H2 , . . . , Ht (which are possibly empty)Ssuch that H1 is a Hall graph in G and, for each 2 ≤ i ≤ t, the graph Hi is a Hall graph in G \ j<i Hj , we define recursively ! t t−1 [ [ G\ Hi := G \ Hi \ Ht . i=1

We may refer to G \

i=1

St

i=1 Hi as a residual graph of G.

We record some basic properties of residual graphs which will be useful later. Observation 2.9. Let G = (X, Y, E) be a bipartite graph. Given bipartite graphs H1 , H2 , . . . , Ht such that H1Sis a Hall graph in G0 := G and, for each 2 ≤ i ≤ t, the graph Hi is a Hall graph in Gi−1 := G \ j<i Hj , the following holds by construction. • For 1 ≤ j ≤ t, X(Gj ) = X \

Sj

i=1 X(Hi ).

• For 1 ≤ j ≤ t, NG (X(Gj )) = Y (Gj ). • For 1 ≤ i < j ≤ t, X(Gj ) ⊆ X(Gi ). The following lemma shows that residual graphs interact well with Hall graphs: a union of Hall graphs taken in successive residual graphs is itself a Hall graph in the original graph. Lemma 2.10. Let G = (X, Y, E) be a bipartite graph. Let H1 , H2 , . . . , Ht be bipartite graphs S such that H1 is a Hall graph in G and, for each 2 ≤ j ≤ t, the graph Hj is a Hall graph in G \ i<j Hi . S Then tj=1 Hj is a Hall graph in G.

12

Proof. Set H :=

St

j=1 Hj , G0 := G, and Gj := Gj−1 \ Hj for 1 ≤ j ≤ t. An induction on j shows

Gj = G[ X \

[

X(Hi ), NG (X \

[

X(Hi )) ],

i≤j

i≤j

so every x ∈ X(Gj ) has all of its G-neighbors inside V (Gj ). In particular, if i < j, then X(Gj−1 ) ⊆ X(Gi ), and hence Y (Gj−1 ) = NG (X(Gj−1 )) ⊆ NG (X(Gi )) = Y (Gi ). We first show that H admits an X(H)-saturating matching. For each j, fix an X(Hj )-saturating matching Mj of Hj , which exists since Hj is a Hall graph in Gj−1 . We have that X(H1 ), . . . , X(Ht ) are pairwise disjoint, because X(H Fj ) ⊆ X(Gj−1 ) and X(Gj−1 ) ∩ X(Hi ) = ∅ for every i < j by the definition of Gj−1 . Hence M := tj=1 Mj is a set of edges where for each edge the X-endpoint of the edge in M lies in exactly one X(Hj ), and the Y -endpoint of the edge lies in Y (Hj ) for the same j. To see that M is a matching, suppose e ∈ Mi and e′ ∈ Mj with i < j share an endpoint. That endpoint cannot lie in X, since X(Hi ) ∩ X(Hj ) = ∅; so it lies in Y , and is then a Y -endpoint of e′ ∈ Mj ⊆ E(Hj ), hence in Y (Hj ) ⊆ Y (Gj−1 ). On the other hand, the same vertex is the Y -endpoint of e ∈ Mi ⊆ E(Hi ), so y ∈ Y (Hi ). Since Hi is a Hall graph in Gi−1 , we have NGi−1 (y) ⊆ X(Hi ). Hence y has no neighbor in X(Gi ), because X(Gi ) ∩ X(Hi ) = ∅, and therefore y ∈ / Y (Gi ). But y ∈ Y (Hj ) ⊆ Y (Gj−1 ) ⊆ Y (Gi ), a contradiction. Hence M is a matching, and it saturates X(H) since each Mj saturates X(Hj ). We next show that NG (Y (H)) ⊆ X(H). Let y ∈ Y (H), so y ∈ Y (Hj ) for some j, and let w ∈ NG (y). Since Hj is a Hall graph in Gj−1 , NGj−1 (y) ⊆ X(Hj ). If w ∈ X(G S j−1 ), then w is a Gj−1 -neighbor of y, so w ∈ X(Hj ) ⊆ X(H). Otherwise w ∈ X \ X(Gj−1 ) = i<j X(Hi ) ⊆ X(H). Either way, w ∈ X(H). Hence H is a Hall graph in G.

3

Saturating Matching in Nets

Fix a (k, α, β)-net G = (X, Y, E) on n ≥ 2 nodes; we assume this throughout the section unless stated otherwise. Our aim is Theorem 3.6: a fast deterministic LOCAL algorithm that computes an X-saturating matching in G. The strategy we use mirrors the one in [24] but it is generalized to our setting. Each vertex x ∈ X computes, using only its local neighborhood in G, a Hall graph Hx in G that contains x on its X-side, together with an X(Hx )-saturating matching of Hx . A tie-breaking rule across X retains a subcollection of these Hall graphs such that every x ∈ X still lies on the X-side of some retained Hall graph, and the saturating matchings inside the retained Hall graphs together form an X-saturating matching of G. Two ingredients drive this strategy. The first is a local existence result: for every x ∈ X, a Hall graph in G containing x on its X-side must exist within a small ball around x. This is the content of Lemma 3.5, the central lemma of the section. Its proof iterates the following step: either the component of the current graph containing x is small enough to serve itself as a Hall graph containing x, or a density based argument extracts a Hall graph from a small ball around x (which, however, need not contain x on its X-side); in the latter case we remove the extracted Hall graph and repeat on the residual graph. Once this process terminates (which it will), the

13

successively removed Hall graphs are glued back together by Lemma 2.10 into a single Hall graph in G containing x. At the heart of the iteration is Lemma 3.4: in a net whose component around x has large radius, some ball around x grows slowly, and the induced bipartite subgraph on such a ball contains a Hall graph (via Lemma 2.7). For this argument to be applied at every step of the iteration, the residual graphs must retain enough structure of a net. This is what the structural lemmas Lemma 3.2 and Lemma 3.3 deliver: components of residual graphs are weak-nets, and are either of small radius — in which case they admit saturating matchings by Lemma 3.1 and can serve as Hall graphs containing x — or are again nets with slightly weaker parameters, on which Lemma 3.4 can be reapplied. The second ingredient is the way the local Hall graphs are used to make a global matching, carried out in the proof of Theorem 3.6. Once each x ∈ X has selected a Hall graph Hx containing it, a consistent tie-breaking rule based on vertex identifiers determines which Hx ’s are retained.

3.1

Saturating Matching in Weak Nets

We now begin with the following matching result. It shows that any weak (k, α, β)-net admits an X-saturating matching. Lemma 3.1. Let k ≥ 2 be an integer and let α, β be positive integers with α ≥ 3 and β ≥ 3. If G = (X, Y, E) is a weak (k, α, β)-net, then G admits an X-saturating matching. Proof. By Hall’s theorem[37], it suffices to show that |NG (S)| ≥ |S| for every S ⊆ X. Suppose ′ for a contradiction that there exists S ⊆ X with |NG (S)| ≤ |S| − 1. We may assume P that G := ′ G[S, NG (S)] is connected, P for if the components of G partition S as S1 ⊔· · ·⊔St , then i |NG (Si )| = |NG (S)| ≤ |S| − 1 = i |Si | − 1, so |NG (Si )| ≤ |Si | − 1 for some i, and we may replace S by Si . Let b be the number of k-bad vertices in G′ , and let g1 and g2 be the numbers of k-good vertices in G′ lying in S and NG (S), respectively. We derive a contradiction by showing that g1 + g2 < b and g1 + g2 ≥ b. Note that every neighbor of x ∈ S lies in NG (S), so by Property 1 the edge count of G′ satisfies |E(G′ )| ≥ (k − 1)(|S| − g1 ) + kg1 = (k − 1)|S| + g1 . On the other hand, again by Property 1, |E(G′ )| ≤ (k − 1)(|NG (S)| − b − g2 ) + kb + (k − 2)g2 = (k − 1)|NG (S)| + b − g2 . Combining the above two inequalities with |NG (S)| ≤ |S| − 1 yields g1 + g2 ≤ b − (k − 1) < b, since k ≥ 2. To show g1 + g2 ≥ b, we show an injection from the k-bad vertices of G′ into the k-good vertices of G′ . Let v be k-bad in G′ (which implies v ∈ Y (G′ ) as well). Then k = degG’ (v) ≤ degG (v) ≤ k, so v is also k-bad in G, and by Property 2 there exists a k-good node in G within distance α in G from v. Fix a path Pv from v to the closest such k-good node, say w(v), in G, and let z(v) denote the last vertex of Pv that lies in V (G′ ). We claim that v 7→ z(v) is a well-defined injection from Vbad (G′ , k) into Vgood (G′ , k). Note first that z(v) ̸= v. Suppose for contradiction that z(v) = v. Since v is k-bad in G, it is not k-good in G, so w(v) ̸= v and Pv has length at least one. Then the successor of v along Pv lies outside V (G′ ); since v ∈ NG (S) ⊆ Y , all neighbors of v lie in X, so this successor is in X \ S. Hence degG’ (v) < degG (v) = k, contradicting that v is k-bad in G′ .

14

Note next that every internal vertex u of Pv is k-neutral in G. Indeed, u is not k-good in G by minimality of dG (v, w(v)), and u is not k-bad in G either, since u ̸= v and dG (v, u) ≤ α − 1 < βα would violate Property 3. We now show that z(v) is k-good in G′ . Suppose first that z(v) = w(v). Then z(v) is k-good in G, and this status is preserved in G′ : if z(v) ∈ X then all its neighbors remain in G′ and degG’ (z(v)) = degG (z(v)) ≥ k; if z(v) ∈ Y then degG’ (z(v)) ≤ degG (z(v)) ≤ k − 2. Now suppose that z(v) ̸= w(v). Then z(v) is internal to Pv , hence k-neutral in G, and the successor of z(v) along Pv lies outside V (G′ ). Consequently z(v) ∈ / S, for otherwise every neighbor of z(v) would lie in NG (S) ⊆ V (G′ ). Therefore z(v) ∈ NG (S) ⊆ Y and has at least one neighbor outside V (G′ ), giving degG’ (z(v)) ≤ degG (z(v)) − 1 = k − 2. Finally, we verify injectivity. Suppose v1 ̸= v2 are both k-bad in G′ with z(v1 ) = z(v2 ) = z. The subpath of Pvi from vi to z lies entirely in V (G′ ), so dG (vi , z) ≤ α, and hence dG (v1 , v2 ) ≤ 2α. On the other hand, since both v1 and v2 are k-bad in G, Property 3 gives dG (v1 , v2 ) ≥ βα ≥ 3α, contradicting the previous bound. Combining the two parts, b ≤ g1 + g2 < b, a contradiction. Therefore |NG (S)| ≥ |S| for every S ⊆ X, and by Hall’s theorem G admits an X-saturating matching.

3.2

Structural Properties of Residual Graphs

When we remove a Hall graph (or multiple ones) from a (k, α, β)-net, the residual graph remaining need no longer satisfy Property 2. The next lemma says that within each component of this residual graph, every Y -vertex either lies in a small-radius component, or still has a nearby k-good vertex —albeit at the cost of this good node now only being within distance 3α instead of α. Lemma 3.2. Let k ≥ 1 be an integer and let α, β be positive integers with α ≥ 3 and β ≥ 3. Let G = (X, Y, E) be a (k, α, β)-net, and set G0 := G. For 1 ≤ i ≤ j, let Hi be a Hall graph (possibly empty) in Gi−1 and let Gi := Gi−1 \ Hi . Let C be a connected component of Gi for some 0 ≤ i ≤ j, and let w ∈ Y ∩ V (C). Then at least one of the following holds: • rad(C) is at most 3α; • w lies within distance 3α in Gi of a vertex that is k-good in Gi . Proof. All distances below are measured in G0 unless otherwise stated. Suppose rad(C) exceeds 3α; we produce a vertex that is k-good in Gi within distance 3α of w in Gi . A straightforward induction on i shows that G0 [ Si , NG0 (Si ) ] ⊆ Gi , where Si := X ∩ V (Gi ). Indeed, the claim is immediate for i = 0, and if it holds for some i ≥ 0, then every x ∈ Si has all of its G0 -neighbors, together with the incident edges, inside Gi ; hence NGi (S ′ ) = NG0 (S ′ ) for every S ′ ⊆ Si . Since Gi+1 = Gi [ Si+1 , NGi (Si+1 ) ] by definition and Si+1 ⊆ Si , we get Gi+1 ⊇ G0 [ Si+1 , NG0 (Si+1 ) ], as claimed. Consequently, every x ∈ Si has all of its neighbors in G0 inside V (Gi ), and so any path in G0 that leaves V (Gi ) must do so from a vertex in Y . By Property 2 there exists z ∈ V (G0 ) that is k-good in G0 with d(w, z) ≤ α; fix a shortest path ′ P1 from w to z in G0 . The internal vertices of P1′ are not k-good in G0 by minimality of d(w, z), and by Property 3 at most one of them is k-bad in G0 , since any two internal vertices of a path of length at most α lie at distance at most α − 2 < βα. Let v denote this bad vertex if it exists; the remaining internal vertices of P1′ are k-neutral in G0 . Let P1 be the maximal subpath of P1′ starting at w whose vertices all lie in V (Gi ), and let u1 be its last vertex. Then P1 is a path in Gi , so dGi (w, u1 ) ≤ |P1 |. Suppose first that u1 ̸= v. If u1 = z, then z ∈ V (Gi ), and it is still k-good in Gi : if z ∈ X then all its neighbors remain in Gi and degGi (z) = degG0 (z) ≥ k; if z ∈ Y then degGi (z) ≤ degG0 (z) ≤ k −2. 15

Otherwise u1 is internal to P1′ and distinct from v, hence k-neutral in G0 ; since any path in G0 that leaves V (Gi ) must do so from a vertex in Y , we have u1 ∈ Y , and since the successor of u1 on P1′ lies outside V (Gi ), we have degGi (u1 ) ≤ degG0 (u1 ) − 1 = k − 2. In either case u1 is k-good in Gi and dGi (w, u1 ) ≤ |P1′ | ≤ α ≤ 3α. Now suppose u1 = v. If v loses at least two neighbors in passing from G0 to Gi , then degGi (v) ≤ k − 2, so v is k-good in Gi and we are done as before. We may therefore assume v loses exactly one neighbor, so degGi (v) = k − 1. Note that |P1 | = d(w, v) is even, since w ∈ Y and v ∈ Y . Combined with |P1 | ≤ |P1′ | − 1 ≤ α − 1 (as v is internal to P1′ ), this yields ( α − 2 if α is even, |P1 | ≤ α − 1 if α is odd. Set

( α λ := α+1

if α is even, if α is odd.

Since rad(C) exceeds 3α, eccC (v) is greater than 3α, and hence greater than λ. Thus there is a shortest path P2 in C of length exactly λ starting at v. Let v ∗ denote its other endpoint; since C is a connected component of Gi , we have dGi (v, v ∗ ) = λ. Since λ is even and v ∈ Y , we have v ∗ ∈ Y . Among all vertices that are k-good in G0 , choose z ′ to minimize d(v ∗ , z ′ ); by Property 2 applied to v ∗ , d(v ∗ , z ′ ) ≤ α. Fix a shortest path P3′ from v ∗ to z ′ in G0 . We first claim that every internal vertex of P3′ other than v is k-neutral in G0 . Indeed, such a vertex is not k-good in G0 by the minimality of d(v ∗ , z ′ ). It is also not k-bad in G0 : a k-bad vertex b ̸= v on P3′ would satisfy d(b, v) ≤ d(b, v ∗ ) + d(v ∗ , v) ≤ |P3′ | + λ ≤ 2α + 1 < 3α ≤ βα, using α ≥ 3 and β ≥ 3, contradicting Property 3, since both b and v are k-bad in G0 . Let P3 be the maximal subpath of P3′ starting at v ∗ whose vertices all lie in V (Gi ), and let u3 be its last vertex. Note that any two consecutive vertices of P3′ that both lie in V (Gi ) are joined by an edge of Gi , since one of them lies in X ∩ V (Gi ) and every such vertex retains all of its G0 -neighbors and incident edges in Gi ; hence P3 is a path in Gi and dGi (v ∗ , u3 ) ≤ |P3 | ≤ α. We next claim that u3 ̸= v. If v lies on P3′ , then v is internal to P3′ : indeed v ̸= z ′ , since z ′ is k-good in G0 while v is k-bad in G0 , and v ̸= v ∗ , since dGi (v, v ∗ ) = λ > 0. The subpath of P3′ from v ∗ to v then has length at most |P3′ | − 1 ≤ α − 1 < λ = dGi (v ∗ , v). Hence this subpath is not a path in Gi , so it contains a vertex outside V (Gi ), and therefore P3 ends strictly before v. In particular u3 ̸= v. On the other hand, if v does not lie on P3′ at all, then trivially u3 ̸= v. We now show that u3 is k-good in Gi . If u3 = z ′ , then z ′ is k-good in G0 which implies it is k-good in Gi as well: if z ′ ∈ X then all its neighbors remain in Gi and degGi (z ′ ) = degG0 (z ′ ) ≥ k; if z ′ ∈ Y then degGi (z ′ ) ≤ degG0 (z ′ ) ≤ k − 2. Otherwise u3 is internal to P3′ and distinct from v, hence k-neutral in G0 by the first claim, and the successor of u3 on P3′ lies outside V (Gi ). Since any path in G0 that leaves V (Gi ) must do so from a vertex in Y , we have u3 ∈ Y , and therefore degGi (u3 ) ≤ degG0 (u3 ) − 1 = k − 2, so u3 is k-good in Gi . Finally, the concatenation P1 + P2 + P3 is a walk in Gi from w to u3 . Its length is bounded: |P1 | + |P2 | + |P3 | ≤ (α − 1) + (α + 1) + α = 3α. Hence dGi (w, u3 ) ≤ 3α, completing the proof.

16

The next lemma examines the structure of residual graphs: every component of a residual graph of a (k, α, β)-net is itself a weak (k, α, β)-net, and is either small (with radius at most βα/2) or a (k, 3α, ⌊β/3⌋)-net. Lemma 3.3. Let k ≥ 1 be an integer and let α, β be positive integers with α ≥ 3 and β ≥ 60. Let G = (X, Y, E) be a (k, α, β)-net, and set G0 := G. For 1 ≤ i ≤ j, let Hi be a Hall graph (possibly empty) in Gi−1 and let Gi := Gi−1 \ Hi . Let C be a connected component of Gi for some 0 ≤ i ≤ j. Then the following holds: 1. C is a weak (k, α, β)-net and, 2. rad(C) is at most βα 2 , or C is a (k, 3α, ⌊β/3⌋)-net. Proof. All distances below are measured in G0 unless otherwise stated. A straightforward induction on i shows that G0 [ Si , NG0 (Si ) ] ⊆ Gi , where Si := X ∩ V (Gi ). Indeed, the claim is immediate for i = 0, and if it holds for some i ≥ 0, then every x ∈ Si has all of its G0 -neighbors, together with the incident edges, inside Gi ; hence NGi (S ′ ) = NG0 (S ′ ) for every S ′ ⊆ Si . Since Gi+1 = Gi [ Si+1 , NGi (Si+1 ) ] by definition and Si+1 ⊆ Si , we get Gi+1 ⊇ G0 [ Si+1 , NG0 (Si+1 ) ], as claimed. Consequently, every x ∈ Si has all of its neighbors in G0 inside V (Gi ), and so any path in G0 that leaves V (Gi ) must do so from a vertex in Y . We first show that C is a weak (k, α, β)-net. The bounds in Property 1 for C are immediate from Property 1 for G0 : any x ∈ X ∩ V (C) lies in Si , so degC (x) = degG0 (x) ≥ k − 1, and any y ∈ Y ∩ V (C) satisfies degC (y) ≤ degG0 (y) ≤ k. For Property 3 for C, let y1 , y2 ∈ Y ∩ V (C) be distinct vertices that are k-bad in C. Then for q ∈ {1, 2}, degG0 (yq ) ≥ degC (yq ) = k and degG0 (yq ) ≤ k, so degG0 (yq ) = k; thus y1 , y2 are k-bad in G0 as well. Since C is an induced subgraph of G0 , distances in C dominate those in G0 , giving dC (y1 , y2 ) ≥ dG0 (y1 , y2 ) ≥ βα by Property 3 for G0 . For Property 2 for C, let y ∈ Y ∩ V (C) be k-bad in C. By Property 2 for G0 , there exists a vertex that is k-good in G0 within distance α of y. Among all vertices that are k-good in G0 , choose z to minimize dG0 (y, z); then dG0 (y, z) ≤ α. Fix a shortest path P ′ from y to z in G0 . Every internal vertex of P ′ is k-neutral in G0 : it cannot be k-good in G0 since it lies strictly closer to y than z does, contradicting the minimality of dG0 (y, z); and it cannot be k-bad in G0 , since such a vertex u would be distinct from y and satisfy d(y, u) ≤ |P ′ | − 1 ≤ α − 1 < βα, contradicting Property 3 for G0 . Let P be the maximal subpath of P ′ starting at y whose vertices all lie in V (Gi ), and let v be its last vertex. Since y is k-bad in C, its degree in Gi equals its degree in G0 , so all of its neighbors in G0 lie in V (Gi ); in particular the second vertex of P ′ lies in V (Gi ), so v ̸= y. If v = z, then z ∈ V (Gi ) and it is k-good in Gi as it is so in G0 : a vertex in X ∩ V (Gi ) retains all its neighbors in G0 , so degGi (z) = degG0 (z) ≥ k when z ∈ X, and a vertex in Y can only lose neighbors, giving degGi (z) ≤ degG0 (z) ≤ k − 2 when z ∈ Y . Otherwise v is internal to P ′ , hence k-neutral in G0 , and the successor of v on P ′ lies outside V (Gi ). Since any path in G0 that leaves V (Gi ) must do so from a vertex in Y , this forces v ∈ Y , so degGi (v) ≤ degG0 (v) − 1 = k − 2. In either case v is k-good in Gi , and dGi (y, v) ≤ |P | ≤ α. Since degrees and distances inside C match those in Gi , v is k-good in C, and dC (y, v) ≤ |P | ≤ α This verifies Property 2 for C, completing the proof that C is a weak (k, α, β)-net. This gives that Instance 1 holds. We now use Lemma 3.2, whose assumptions (α ≥ 3 and β ≥ 3) hold here. It gives that either rad(C) is at most 3α, or every w ∈ Y ∩ V (C) lies within distance 3α in Gi of a vertex that is k-good in Gi . Suppose first that rad(C) is at most 3α. Since β ≥ 60 gives βα 2 ≥ 30α ≥ 3α, rad(C) is at most βα 2 . 17

Suppose instead that every w ∈ Y ∩V (C) lies within distance 3α in Gi of a vertex that is k-good in Gi . Since degrees and distances inside a component of Gi match those in Gi , this gives that every w ∈ Y ∩ V (C) lies within distance 3α in C of a vertex that is k-good in C, which is the condition of Property 2 for C as a (k, 3α, ⌊β/3⌋)-net. Combined with the degree bounds already established and with the fact that for any two k-bad vertices y1 , y2 in C dC (y1 , y2 ) ≥ βα ≥ ⌊β/3⌋ · 3α (using 3⌊β/3⌋ ≤ β), C is a (k, 3α, ⌊β/3⌋)-net. This gives that Instance 2 holds.

3.3

Existence of Hall Graphs in Nets

We now come to the argument at the core of this section. If the component of G containing x has large radius, then balls around x cannot all grow geometrically, so at some distance t the ball BG (x, t) grows by a factor of at most 1 + ϵ for an ϵ > 0 we choose . The net structure provides a lower bound on k-good vertices and an upper bound on k-bad vertices in this ball, and these bounds combine via an edge-counting argument to show that the induced bipartite subgraph on BG (x, t) has at least as many Y -vertices as X-vertices; Lemma 2.7 then yields a Hall graph. The strategy behind the following lemma — locating a slowly growing ball around x in which the Y -side is at least as large as the X-side, and extracting a Hall graph from it via Lemma 2.7 — is due to [24], where a weaker analogue of the lemma is proved in a more restrictive setting where there are no k-bad and k-neutral nodes in G. Our version generalizes theirs to (k, α, β)-nets; the presence of k-bad as well as k-neutral vertices requires a more delicate argument inside the ball. Lemma 3.4. Let G = (X, Y, E) be a (k, α, β)-net on n vertices with k ≥ 2, α ≥ 3, β ≥ 60, and maximum degree ∆ ≥ 2. Let x ∈ X and let C be the connected component of G containing 1 x. Let ϵ be a real number with 0 < ϵ ≤ 3(k+1)∆ α+2 , let s := 4α + 6, let L be an integer with L ≥ ⌈log1+ϵ (n)⌉ + 1, and let t0 be an even integer with t0 > max{βα, 10∆α+2 }. If rad(C) is at least t0 + s(L − 1), then there exists an even integer t with t0 ≤ t ≤ t0 + s(L − 1) such that |BG (x, t)| ≤ (1 + ϵ) · |BG (x, t − s)|, and the induced bipartite subgraph G[ X ∩ BG (x, t), Y ∩ BG (x, t) ] contains a non-empty Hall graph in G. Proof. We begin by finding an even integer t in T := {t0 , t0 + s, . . . , t0 + s(L − 1)} for which |BG (x, t)| ≤ (1 + ϵ) · |BG (x, t − s)|. Suppose for contradiction that |BG (x, t)| > (1 + ϵ) · |BG (x, t − s)| for every t ∈ T . Applying this inequality along the L elements of T in succession, |BG (x, t0 + s(L − 1))| > (1 + ϵ)L · |BG (x, t0 − s)| ≥ (1 + ϵ)L . Since L ≥ log1+ϵ (n) + 1, the right-hand side is at least (1 + ϵ)n > n, contradicting |BG (x, t0 + s(L − 1))| ≤ n. Hence some such t exists, and by construction t is even and t ≥ t0 . Fix it for the remainder of the proof. Set X ∗ := X ∩ BG (x, t),

Y ∗ := Y ∩ BG (x, t),

G′ := G[X ∗ , Y ∗ ],

B ′′ := BG (x, t − s).

By the choice of t, |G′ | ≤ (1 + ϵ) |B ′′ |. Since t is even and x ∈ X, every y ∈ Y ∗ satisfies dG (x, y) ≤ t−1, so every G-neighbor of y lies within distance at most t from x and therefore in X ∗ ; consequently NG (Y ∗ ) ⊆ X ∗ . 18

Moreover G′ has no isolated vertices: x has at least k − 1 neighbors in BG (x, 1) ⊆ V (G′ ), and every other v ∈ V (G′ ) has, as the predecessor on a shortest x–v path, a G-neighbor at distance less than t from x, which lies in V (G′ ). The remainder of the proof is devoted to showing that |X ∗ | ≤ |Y ∗ |. The argument proceeds in three parts. First, we observe that the lemma follows once this inequality is established. Then, writing G := Vgood (G, k) ∩ V (G′ ),

B := Vbad (G, k) ∩ V (G′ ),

N := Vneutral (G, k) ∩ V (G′ ),

we bound |G| from below, and bound |B| from above. Finally, we double-count the edges of G′ in two ways, and make use of these bounds on G and B to prove that |Y ∗ | − |X ∗ | is non-negative which gives the desired inequality |X ∗ | ≤ |Y ∗ |. We start with the reduction. Claim 1. |X ∗ | ≤ |Y ∗ | implies that there exists a Hall graph H in G. By lemma 2.7, since G′ has no isolated nodes, there is a non-empty Hall graph H in G′ . Moreover, since NG (Y ∗ ) ⊆ X ∗ , every y ∈ Y (H) ⊆ Y ∗ satisfies NG (y) = NG′ (y), so NG (Y (H)) = NG′ (Y (H)) ⊆ X(H) and H is a Hall graph in G as well. We now move on to bound G and B. |B ′′ | . ∆α+2 We first observe that every vertex of C lies within distance α + 1 of a vertex in Vgood (G, k). Indeed, let w ∈ V (C). If w ∈ Y , then Property 2 for G ensures a vertex u ∈ Vgood (G, k) with dG (w, u) ≤ α, and clearly u ∈ V (C). If w ∈ X and w ∈ Vgood (G, k), take u = w. Otherwise w ∈ X is not k-good in G, so degG (w) = k − 1 by Definition 2.1, which is at least 1 since k ≥ 2. Hence w has a neighbor y ′ ∈ Y ∩ V (C), and applying Property 2 for G to y ′ produces u ∈ Vgood (G, k) ∩ V (C) with dG (w, u) ≤ dG (w, y ′ ) + dG (y ′ , u) ≤ 1 + α. Claim 2. |G| ≥

Now, for each w ∈ B ′′ choose a vertex v(w) ∈ Vgood (G, k) with dG (w, v(w)) ≤ α + 1, which exists just as we saw now. Since s = 4α + 6, by triangle inequality dG (x, v(w)) ≤ dG (x, w) + (α + 1) ≤ (t − s) + (α + 1) = t − 3α − 5 < t, so v(w) ∈ V (G′ ) and hence v(w) ∈ G. We now count how many w ∈ B ′′ can share the same image v(w) = v. Any such w satisfies dG (w, v) ≤ α + 1, so it lies in BG (v, α + 1); and a vertex with maximum degree ∆ has α+1 X |BG (v, α + 1)| ≤ ∆i ≤ ∆α+2 i=0

since ∆ ≥ 2. Therefore at most ∆α+2 vertices of B ′′ are mapped to any single v ∈ G, and |G| ≥

|B ′′ | . ∆α+2

The claim is hence true. We now bound |B| from above. ′′ Claim 3. |B| ≤ 1 + 20 β |G| + ϵ |B |.

19

Set ℓ := ⌈βα/4⌉; since β ≥ 60 and α ≥ 3, we get ℓ ≥ 15α. We partition B by distance from x into three regions: Bnear := {b ∈ B : dG (x, b) < ℓ}, Bcore := {b ∈ B : ℓ ≤ dG (x, b) ≤ t − (α + 1)}, Bshell := {b ∈ B : dG (x, b) > t − (α + 1)}. Any two distinct b1 , b2 ∈ Bnear would satisfy dG (b1 , b2 ) ≤ dG (b1 , x) + dG (x, b2 ) < 2ℓ < βα, contradicting Property 3 of G since both lie in Vbad (G, k). Hence |Bnear | ≤ 1. Moreover, since α + 1 < s, the definition of Bshell implies dG (x, b) > t − s for any b ∈ Bshell , so Bshell ⊆ V (G′ ) \ B ′′ and therefore |Bshell | ≤ |G′ | − |B ′′ | ≤ ϵ |B ′′ | by the choice of t. It remains to bound |Bcore |. Fix b ∈ Bcore and a shortest path Pb from x to b in G. Since dG (x, b) ≥ ℓ, the last ℓ + 1 vertices of Pb form a path b = u0 , u1 , . . . , uℓ with dG (x, ui ) = dG (x, b) − i, so every ui ∈ V (G′ ). Set M := ⌊ℓ/(2α + 3)⌋ and ij := j(2α + 3) for 0 ≤ j ≤ M , so each ij ∈ {0, . . . , ℓ}. By the observation proved at the start of the previous claim, for each j there exists gj (b) ∈ Vgood (G, k) with dG (uij , gj (b)) ≤ α + 1; then dG (x, gj (b)) ≤ dG (x, uij ) + (α + 1) ≤ dG (x, b) + (α + 1) ≤ t, so gj (b) ∈ G. Set G(b) := {g0 (b), . . . , gM (b)}. We claim that |G(b)| = M + 1 and that the sets G(b) are pairwise disjoint as b ranges over Bcore . For distinctness within G(b): if gj (b) = gj ′ (b) with j ̸= j ′ , then dG (uij , uij ′ ) ≤ 2(α + 1), while u0 , . . . , uℓ is a subpath of a shortest path and so dG (uij , uij ′ ) = |ij − ij ′ | ≥ 2α + 3, a contradiction. For disjointness across Bcore : if g ∈ G(b) ∩ G(b′ ) with b ̸= b′ , then, using dG (b, uij ) = ij ≤ ℓ, dG (b, b′ ) ≤ dG (b, uij ) + dG (uij , g) + dG (g, u′ij ′ ) + dG (u′ij ′ , b′ ) ≤ 2ℓ + 2(α + 1) < βα, contradicting Property 3 since both b, b′ lie in Vbad (G, k). Since 2α + 3 ≤ 5α and ℓ = ⌈βα/4⌉, we have ℓ β ℓ ≥ ≥ . M +1 ≥ 2α + 3 5α 20 The sets G(b) are therefore pairwise disjoint subsets of G, so β |G| ≥ (M + 1) |Bcore | ≥ 20 |Bcore |,

which gives the inequality |Bcore | ≤

20 |G|. β

Summing over the upper bounds on |Bcore |, |Bshell | and |Bnear | yields the claim. Having bounded |G| from below and |B| from above, we proceed to the edge count that links these bounds to the term |Y ∗ | − |X ∗ |. Set ∗ Xint := X ∗ ∩ BG (x, t − 2),

20

∗ ∗ Xbd := X ∗ \ Xint .

∗ , every G-neighbor of x′ lies at distance at most t − 1 from x and hence in Y ∗ , so For x′ ∈ Xint degG’ (x′ ) = degG (x′ ). Since G is a (k, α, β)-net, degG (x′ ) ≥ k − 1 for any vertex of X , with degG (x′ ) ≥ k exactly when x′ ∈ Vgood (G, k). Counting edges from the X-side, X X ∗ ∗ |E(G′ )| = degG’ (x′ ) ≥ degG (x′ ) ≥ (k − 1)|Xint | + |Xint ∩ Vgood (G, k)|. ∗ x′ ∈Xint

x′ ∈X ∗

From the Y -side, NG (Y ∗ ) ⊆ X ∗ gives degG’ (y) = degG (y) for every y ∈ Y ∗ , where degG (y) ≤ k−2 if y ∈ Vgood (G, k), degG (y) = k if y ∈ Vbad (G, k), and degG (y) = k − 1 if y ∈ Vneutral (G, k). Therefore X |E(G′ )| = degG (y) ≤ (k − 1)|Y ∗ | − |Y ∗ ∩ Vgood (G, k)| + |Y ∗ ∩ Vbad (G, k)|. y∈Y ∗

Comparing the two inequalities and rearranging,
∗ ∗ (k − 1) |Y ∗ | − |Xint | ≥ |Xint ∩ Vgood (G, k)| + |Y ∗ ∩ Vgood (G, k)| − |Y ∗ ∩ Vbad (G, k)|.

(3)

Since G ⊆ X ∗ ⊔ Y ∗ , we have that ∗ ∗ |Xint ∩ Vgood (G, k)| + |Y ∗ ∩ Vgood (G, k)| ≥ |G| − |Xbd |;

(4)

and, since every k-bad vertex in G lies in Y by Definition 2.2, |Y ∗ ∩ Vbad (G, k)| = |B|.

(5)

∗ | to both sides in Equation (3) and substituting the bounds from Equations (4) Adding −(k −1)|Xbd and (5) gives
∗ |. (k − 1) |Y ∗ | − |X ∗ | ≥ |G| − |B| − k |Xbd ∗ | and verify that the right-hand It now remains to substitute the bounds on |G|, |B|, and |Xbd 20 ∗ ⊆ V (G′ ) \ B ′′ since side is non-negative. By the bound on |B|, |B| ≤ 1 + β |G| + ϵ|B ′′ |. Also Xbd ∗ | ≤ ϵ|B ′′ | by the choice of t. Using β ≥ 60, t − 2 ≥ t − s, so |Xbd  
∗ ∗ ∗ 20 (k −1) |Y |−|X | ≥ |G|−|B|−k |Xbd | ≥ 1− β |G|−1−(k +1)ϵ|B ′′ | ≥ 23 |G|−1−(k +1)ϵ|B ′′ |.

The lower bound on |G| ( that |G| ≥ |B ′′ |/∆α+2 ) and the assumption (k + 1)ϵ ≤ 1/(3∆α+2 ) from the lemma statement yields
(k − 1) |Y ∗ | − |X ∗ | ≥

|B ′′ | − 1. 3∆α+2

Finally, rad(C) is at least t ≥ t0 , so eccC (x) is at least t0 and C contains vertices at every distance from x between 0 and t0 , giving |B ′′ | ≥ (t0 −s)+1. Since t0 > 10∆α+2 and s = 4α+6, |B ′′ | ≥ 3∆α+2 , and the right-hand side is non-negative. As k ≥ 2, this gives |X ∗ | ≤ |Y ∗ | and we are done. the above inequality with the fact that k ≥ 1 and α ≥ 3, we get that We now combine Lemmas 3.1, 3.3 and 3.4 to prove the central lemma of this section: every x ∈ X is contained in the X-side of a Hall graph lying in a small ball around x. The construction iterates the following: at each step, either the component of the current residual graph containing x has small radius and serves as the next Hall graph (via Lemmas 3.1 and 3.3), or Lemma 3.4 produces a Hall graph in a small ball around x. The iteration halts as soon as x lies in the X-side 21

of the Hall graph just produced, and terminates in finitely many steps because each removal strictly shrinks |X|. Lemma 2.10 then glues the resulting Hall graphs into a single one. Lemma 2.10 then glues the resulting Hall graphs into a single one. The overall shape of the above construction–iteratively removing Hall graphs from the current residual graph until one containing x on its X-side is produced–follows [24]. In their setting, the residual graphs retain the same strong structural properties as the original graph, so the same lemma applies at every step with no additional work. In our weaker setting, removing a Hall graph from a net degrades its structure: the residual graph is no longer a net, only a weak-net, and its components are nets with weaker parameters. Controlling this degradation is exactly the role of the structural lemmas Lemma 3.2 and Lemma 3.3, which ensure that the argument of Lemma 3.4 can be reapplied inside the iteration. Lemma 3.5. Let G = (X, Y, E) be a (k, α, β)-net on n vertices with k ≥ 2, α ≥ 3, β ≥ 180, and maximum degree ∆ ≥ 2. Then, for x ∈ X and κ(n) := 600kα∆3α+2 log n + 4βα, there exists a Hall graph H in G such that x ∈ X(H) and V (H) ⊆ BG (x, κ(n)). Proof. We build H as a finite union of Hall graphs H1 , . . . , Hm in a sequence of bipartite graphs G0 := G and Gi+1 := Gi \ Hi+1 , halting once x ∈ X(Hm ). At each step the connected component of Gi containing x either has radius at most κ(n) 2 , in which case it serves as Hi+1 directly, or κ(n) has radius at least 2 in which case Lemma 3.4 extracts a Hall graph from BGi (x, κ(n)). Each Hj is non-empty, so |X(Gi )| strictly decreases and the process terminates; and each Hj satisfies V (Hj ) ⊆ BGj−1 (x, κ(n)), hence V (Hj ) ⊆ BG (x, κ(n)). ′ Set α′ := 3α and β ′ := ⌊β/3⌋, and set t0 := 2(β ′ α′ + 10∆α +2 ) = 2(⌊β/3⌋ · 3α + 10∆3α+2 ), ′ s := 4α′ + 6 = 12α + 6, ϵ := 1/(3(k + 1)∆α +2 ) = 1/(3(k + 1)∆3α+2 ), and L := ⌈log1+ϵ (n)⌉ + 1. Observe that L − 1 = ⌈log

1+

1 3(k+1)∆3α+2

n⌉ ≤ ⌈9(k + 1)∆3α+2 log n⌉ ≤ 20k∆3α+2 log n.

Combining the above inequality with the facts that k ≥ 2 and α ≥ 3, and using ⌊β/3⌋ · 3 ≤ β,

t0 + s(L − 1) ≤ 2 ⌊β/3⌋ · 3α + 10∆3α+2 + (12α + 6) 20k∆3α+2 log n ≤ 2βα + 20∆3α+2 + 280kα∆3α+2 log n ≤ 2βα + 300kα∆3α+2 log n κ(n) . = 2 Given Gi with x ∈ X(Gi ), let Ci denote the connected component of Gi containing x. By Lemma 3.3 applied with j = i, Ci is a weak (k, α, β)-net, and either has radius at most βα/2 ≤ κ(n) or is a (k, 3α, ⌊β/3⌋)-net. Suppose first that rad(Ci ) is at most t0 + s(L − 1). Then V (Ci ) ⊆ BGi (x, κ(n)), and since Ci is a weak (k, α, β)-net, Lemma 3.1 gives an X(Ci )-saturating matching in Ci . Combined with NGi (Y (Ci )) ⊆ X(Ci ), which follows from Ci being a connected component of Gi , this makes Hi+1 := Ci a Hall graph in Gi with x ∈ X(Hi+1 ) and V (Hi+1 ) ⊆ BGi (x, κ(n)). Halt with m := i + 1. Suppose instead that rad(Ci ) is greater than t0 +s(L−1), so by Lemma 3.3 it is a (k, 3α, ⌊β/3⌋)net. Since rad(Ci ) exceeds t0 +s(L−1) ≥ βα 2 , applying Lemma 3.4 to Ci at x produces a non-empty Hall graph Hi+1 in Gi with V (Hi+1 ) ⊆ BGi (x, t0 + s(L − 1)) ⊆ BGi (x, κ(n)). If x ∈ X(Hi+1 ), halt with m := i + 1; otherwise pass to Gi+1 and continue. 22

Each Hi+1 is non-empty, so |X(Gi+1 )| < |X(Gi )|; this strictly decreasing sequence of nonnegative integers forces the process to halt in at most |X| iterations, and since x ∈ X(Gi ) until the halting step, halting is reached with S x ∈ X(Gm−1 ). It remains to verify that H := m j=1 Hj satisfies the three required conditions. S By construction H1 is a Hall graph in G0 = G and, for 2 ≤ j ≤ m, Hj is a Hall graph in G \ i<j Hi , so H is a Hall graph in G by Lemma 2.10. The halting condition gives x ∈ X(Hm ) ⊆ X(H). Finally, for every v ∈ V (Hj ) we have v ∈ BGj−1 (x, κ(n)), i.e. dGj−1 (x, v) ≤ κ(n). By Observation 2.9, Gj−1 is an induced subgraph of G, so dG (x, v) ≤ dGj−1 (x, v) ≤ κ(n). Hence V (H) ⊆ BG (x, κ(n)).

3.4

Algorithm for Saturating Matching in Nets

With Lemma 3.5 in hand, we are ready to prove the main theorem of the section. The algorithm has each x ∈ X construct a local Hall graph Hx containing it, together with a X(Hx )-saturating matching. Using a consistent tie-breaking rule, each x ∈ X selects a unique Hall graph in which it is contained and consequently a unique “local matching” edge in which it is contained. Showing that these local matchings together form a global matching gives an X-saturating matching. This is virtually the same argument from [24]. Theorem 3.6. Let k ≥ 2 be an integer and let α, β be positive integers with α ≥ 3 and β ≥ 180. There is a deterministic LOCAL algorithm that, given a (k, α, β)-net G = (X, Y, E) on n vertices with maximum degree ∆ ≥ 2, computes an X-saturating matching in O(kα∆3α+2 log n+βα) rounds. Proof. Set r := 600kα∆3α+2 log n + 4βα. We now describe the algorithm. In the first r + 1 rounds, each x ∈ X collects the ball BG (x, r + 1). By Lemma 3.5, there exists a Hall graph H in G with x ∈ X(H) and V (H) ⊆ BG (x, r). For any candidate subgraph H with V (H) ⊆ BG (x, r), both defining conditions of Definition 2.6 — the existence of an X(H)-saturating matching, and NG (Y (H)) ⊆ X(H) — depend only on the subgraph of G induced on BG (x, r + 1), since every G-neighbor of a vertex of V (H) lies in BG (x, r+1). Hence x can enumerate all candidate subgraphs and test both conditions by local computation. Each vertex x sets (Hx , Mx ) to be the first pair, in some fixed canonical order (say, lexicographic with respect to the identifier sequences of the candidates), consisting of a Hall graph Hx in G with x ∈ X(Hx ) and V (Hx ) ⊆ BG (x, r) and an X(Hx )-saturating matching Mx of Hx . In the next r + 1 rounds, each x ∈ X collects (Hx′ , Mx′ ) from every x′ ∈ BG (x, r + 1) ∩ X. For each x ∈ X, set  H(x) := x′ ∈ X : x ∈ X(Hx′ ) . We record two properties of H(x). First, H(x) is non-empty, since x ∈ H(x). Second, every x′ ∈ H(x) satisfies dG (x, x′ ) ≤ r, because x ∈ V (Hx′ ) ⊆ BG (x′ , r). In particular, x has collected (Hx′ , Mx′ ) for every x′ ∈ H(x). Each x ∈ X now sets x⋆ to be the vertex of H(x) with the largest identifier, and lets ex be the edge of Mx⋆ incident on x. This edge exists and is unique since x ∈ X(Hx⋆ ) and Mx⋆ is an X(Hx⋆ )-saturating matching. Let M := {ex : x ∈ X} denote the resulting set of edges. We claim that M is an X-saturating matching. Suppose for the sake of contradiction that M is not a matching. Then there exist distinct u, v ∈ X and a vertex z ∈ Y with eu ∩ ev = {z}. The vertex z is an endpoint of eu ∈ Mu⋆ , so z ∈ Y (Hu⋆ ). Similarly, z ∈ Y (Hv⋆ ). Since Hu⋆ and ⋆ Hv are Hall graphs in G, Definition 2.6 gives NG (z) ⊆ X(Hu⋆ ) and NG (z) ⊆ X(Hv⋆ ). Both u and v are G-neighbors of z, hence {u, v} ⊆ X(Hu⋆ ) ∩ X(Hv⋆ ).

23

We distinguish two cases. Suppose first that u⋆ = v ⋆ . Then eu and ev are two edges of Mu⋆ sharing the vertex z, forcing eu = ev . An edge has exactly two endpoints, one of which is z; since both u and v are endpoints distinct from z, we obtain u = v, contradicting u ̸= v. Suppose next that u⋆ ̸= v ⋆ . Without loss of generality, id(v ⋆ ) < id(u⋆ ). From v ∈ X(Hu⋆ ) we have u⋆ ∈ H(v). Then id(v ⋆ ) < id(u⋆ ) contradicts the choice of v ⋆ as the vertex of H(v) with the largest identifier. Both cases yield a contradiction, so M is a matching. Moreover, every x ∈ X is incident to ex ∈ M , so M is X-saturating. The algorithm runs in 2(r+1) = O(kα∆3α+2 log n+βα) rounds.

4

A (∆ + 1)-Edge Coloring Algorithm

Let G = (V, E) be a bipartite graph whose bipartition is unknown to the nodes. In this section, we present an algorithm that computes an (∆ + 1)-edge coloring of G in O(f (∆) log n) rounds. We begin by introducing some definitions and algorithmic subroutines that are used during the execution of the algorithm. The first definition we introduce is the bipartite double cover. Given any graph G, its bipartite double cover is a a virtual bipartite graph obtained by creating two copies of every node in G, one copy on each side of the bipartition. Each copy is adjacent to the copies of the neighbors of its original node on the opposite side. By construction, every node of G knows on which side of the bipartition each of its copies is located, hence when describing an algorithm on the bipartite double cover, we can assume that the nodes of the bipartite double cover know on which side of the bipartition they lie. Definition 4.1 (Bipartite Double Cover). The bipartite double cover of the graph G = (V, E) is a graph Gb = (X, Y, Eb ) where for every node v ∈ V there are nodes vX ∈ X and vY ∈ Y and for every edge (u, v) ∈ E, there is an edge (uX , vY ) and an edge (vX , uY ). We also recall the following folklore result for the bipartite double cover of bipartite graphs. Lemma 4.2. The bipartite double cover of a bipartite graph G consist of two disjoint copies of the graph G. We will make use of two further results during the execution of our algorithm. The first is an existential result about edge coloring on bipartite graphs that will be needed when we take care of coloring small connected components, which we handle with a brute-force approach. Lemma 4.3 (Bipartite edge coloring [18, 43]). Every bipartite graph of maximum degree ∆ admits an edge coloring using ∆ colors. Even stronger, every bipartite graph can be edge colored such that for every edge e = (u, v) the color of e is in the set {1, ..., max(deg(v), deg(u))}. The second result is a result about the sinkless orientation problem, which consists in orienting the edges of the input graph such that every node has one outgoing edge. There is an algorithm solving this problem deterministically in O(log n) rounds for graphs of minimum degree 3. This sinkless orientation algorithm will be used as a subroutine in the algorithm for Lemma 4.6. The sinkless orientation algorithm also works for half-edges which are edges with only one endpoint. Lemma 4.4 (Sinkless orientation, Theorem 1.2 of [35]). For any graph G with minimum degree at least 3, possibly with half-edges, there is a deterministic O(log n)-round algorithm orienting the edges and half-edges of the graph such that every node has an outgoing edge or half-edge.

24

Now that we have introduced the lemmas and definition from the literature that we require in this section, we introduce a new problem that we need to solve in our (∆ + 1)-edge coloring algorithm. We call this problem the Node Selection problem. Definition 4.5 (Node Selection). Let G be a graph and C a clustering associated with this graph such that every node v in G is located in one single cluster. In the Node Selection problem the task is to select one node from each cluster such that no two selected nodes are neighbors in G. Assume that the diameter of each cluster is both greater than 34∆ and in O(f (∆)) for some function f . Then we propose an O(f (∆) log n)-round algorithm solving the Node Selection problem. Lemma 4.6. [Node Selection] Let G a graph of maximum degree ∆ and C a partition of the nodes of the graph into subset of nodes such that every b ∈ C has diameter at least dmin ≥ 34∆ . The NodeSelection(G, C, dmax , ∆) algorithm returns a subset P of the nodes in G such that, 1. At Most One Node Per Cluster: There is no C ∈ C and vp , up ∈ P , such that vp ∈ C,and up ∈ C 2. At Least One Node Per Cluster: For every C ∈ C, there exists vp ∈ P , such that vp ∈ C. 3. No Neighboring Selected Nodes: For every vp , up ∈ P , dG (vp , up ) ≥ 2 The round complexity of NodeSelection(G, C, dmax , ∆) is O(∆ · dmax · log n) We postpone the proof of Lemma 4.6 to Section 4.4.

4.1

Description of the Algorithm

Let G = (V, E) be a bipartite graph whose bipartition is unknown to the nodes. The algorithm first proceeds in ∆ − 2 consecutive phases. During phase i, it computes a subset of the uncolored edges and assigns them the color ∆ − i + 2. It also fully colors the edges of the connected components of small diameter. Every phase is executed on the subgraph induced by the remaining uncolored edges. We define Gi as the graph we consider in phase i. At the end of the ∆ − 2 phases, the algorithm colors the subgraph induced by the remaining uncolored edges using the remaining 3 unused colors (where colors used only for coloring isolated connected components are considered as unused colors). At any phase i of the algorithm, we maintain two invariants. The first invariant is that in the graph induced by uncolored edges, Gi , the degree of any node in the graph is at most ∆ − i + 2. Maintaining this invariant ensures that after ∆−2 phases of the algorithm, the graph G∆−1 induced by uncolored edges has degree at most 3, which we can then color with the three remaining colors. The second invariant bounds the minimum distance between any two nodes of degree ∆ − i + 2. We maintain this distance to be at least di , which is defined via

d∆−2 := 100 d

di−1 := 16 · 11520 · 34∆ i for each 1 ≤ i ≤ ∆ − 2. We now describe phase i of the algorithm. Consider Gi = (V, Ei ) as the induced subgraph of G composed of the edges which where not colored in the previous phases. We let dd = di−1 /11520 be a parameter which we will use in Section 4.2.2. Let Mi = ∅, a set which will contain an intermediary matching of the nodes in Gi , which we use to build a virtual graph in Section 4.2.3. 25

Algorithm 1 EdgeColoring(G = (V, E)) 1: Let G1 be a copy of G and let d∆−2 = 100 2: for i = ∆ − 2 down to 1 do d 3: Let di−1 = 16 · 11520 · 34∆ i 4: for i = 1 to ∆ − 2 do 5: Let dd = di−1 /11520 and let Mi = ∅ 6: Remove from Gi every connected component of diameter less than 16di−1 , and color these components (Section 4.2.1) 7: Let Gb = (X, Y, Eb ) be the bipartite double cover of Gi , from which we remove from X every node of degree strictly less than ∆ − i + 1 8: Let GU be the subgraph of Gi induced by all nodes at distance less than 16dd from a node of degree ∆ − i + 2 9: Compute an MIS S on (Gi \ GU )8dd 10: For every node u ∈ S, add to S a node at distance 2dd + 1 from u in Gi \ GU 11: For every node v of degree ∆ − i + 2, add a node at distance 2dd from vY ; if no such node exists, match the connected component containing vY and add this matching to Mi 12: for each u ∈ S do 13: Add a copy u′Y of uY to Y Compute an X-saturated matching of Gb (by Theorem 3.6) and add it to Mi Let Gb,hso be the graph on V with an edge between u and v if (uX , vY ) ∈ Mi or (vX , uY ) ∈ Mi 16: Let H = (V, E(Gb,hso )) 17: Let Si = SparseNodeSelection(Gi , H, di , ∆) 18: Let Mi′′ be the matching obtained by matching every node except the duplicated nodes and the nodes in Si ▷ Section 4.2.4 19: Color every edge of Mi′′ with color ∆ − i + 2 ▷ Section 4.2.5 20: Remove Mi to obtain Gi+1 21: Edge-color the graph G∆−1 using the colors {1, 2, 3} (Lemma 4.17) 14:

15:

Algorithm 2 SparseNodeSelection(Gi , H, di , ∆) ′

1: Let ∆′ = ∆2di and let dc = 4 · 34∆ 2: Let H ′ be a copy of H

3: Remove from H ′ every node contained in a connected component of weak diameter less than

2dc in Gi 4: Remove from H ′ every node at distance less than 2di from a node of degree ∆ − i + 2 in Gi ,

and every duplicated node 5: Let C = BallCreation(H ′ , dc ) 6: Let H ′′ be a copy of H where we add an edge between two nodes if they are in different clusters and at distance less than 2di in Gi 7: return NodeSelection(H ′′ , C, dc /4, dc /2, ∆′ ) 1. We first handle the connected components of Gi of diameter less than 16di−1 in Section 4.2.1. Each such component is bipartite with every node being of degree at most ∆ − i + 2, and hence admits an edge coloring using colors from the palette {1, . . . , ∆ − i + 2} by Lemma 4.3. An edge colored in phase j < i received either color ∆ − j + 2 which lies outside the palette {1, . . . , ∆ − i + 2} since j < i, or a color in {1, . . . , ∆ − j + 1} if it is inside a small component of Gj ; in the latter case, all vertices of that small component were removed from the graph 26

Algorithm 3 BallCreation(H ′ , dc ) 1: Compute an MIS S on (H ′ )dc 2: For MIS node s ∈ S, compute Bs the cluster containing all of the nodes at distance at most

dc /4 of s in H ′ . 3: return {Bs , for each s in S}

before phase i, so no such edge is adjacent to C. Hence the new coloring is consistent with the partial edge coloring produced so far. 2. We now consider Gb , the bipartite double cover of Gi from which we remove the nodes of degree strictly less than ∆ − i + 1 in Gi . The next step consists in modifying Gb in order to apply Theorem 3.6 which we do in Section 4.2.2. To apply this theorem using Gb , we need Gb to be a (k, α, β)-net as described in Definition 2.2. Property 1 and 3 of the definition are already satisfied for the parameters (∆ − i + 2, 64dd , di−1 /64dd ) as follows. Property 1 is satisfied as every node in X has degree at least ∆ − i + 1 and every node in Y has degree at most ∆ − i + 2. Property 3 is satisfied as the (∆ − i + 2)-bad nodes are at distance di−1 since the bad nodes are only the nodes of degree ∆ − i + 2. To satisfy Property 2, we need every node in Y to be at distance 64dd of a (∆ − i + 2)-good nodes. To achieve this, we duplicate some nodes in Y , so that every node in Y is at distance at most 64dd of a (∆ − i + 2)-good node as follows. We first compute GU , a subgraph of Gi composed of all of the nodes at distance less than 16dd of a node of degree ∆ − i + 2, because we do not want any duplicated node to be part of GU . Then, to decide which nodes will be duplicated, we compute an MIS S on (Gi \ GU )8dd . Then, every node u ∈ S picks arbitrarily one node at distance 2dd + 1 of u in Gi if it exists and adds it to S, which is needed in order to ensure that every node in Y is at distance 64dd of a good node. For the same purpose, every copy vY of a node v of degree ∆ − i + 2 adds a node at distance 2dd of vY in Gb to S. If this is not possible and v has a node of degree strictly less than ∆ − i + 1, it implies that the connected component of Gb (not Gi ) containing vY is of diameter at most 4dd . Notice that this component might not be disconnected in Gi though it is disconnected in Gb because the copy of Gi in Gb removes nodes in X of degree strictly less than ∆ − i + 1. This component does not contain any bad node as vY degree decreased by one compared to v as v has a neighbor of degree stricly less than ∆ − i + 1. In that case, we completely match every node of the component and add it to Mi , the set containing an intermediary matching of Gi . We then duplicate the Y copies of the nodes in S, as follows. For any vY , we create vY′ such that N (vY ) = N (vY′ ). After this step Gb has become a (∆ − i + 2, 64dd , di−1 /64dd )-net (Lemma 4.10). 3. The next step is to compute an X-saturated matching Mi on Gb and to construct a residual graph from the edge of the matching as we do in Section 4.2.3. We use Mi to construct a subgraph H of Gi . The set of nodes of H is the same as the set of nodes of Gi . For every edge (uX , vY ) ∈ Mi , we add the edge (u, v) with an orientation from u to v. If both (uX , vY ) and (vX , uY ) are in Mi , we only construct one edge and do the following. If u is a node of degree which was duplicated, then we orient the edge from u to v, and similarly if v is a node which was duplicated. If not, the nodes orient the edge arbitrarily. 4. Now that H has been computed, the algorithm will use this subgraph to find a matching of the nodes such that the distance between every two unmatched node is at least di . We show

27

how to obtain this in Section 4.2.4. We show how to obtain this in 3 steps. We let ∆′ = ∆2di ′ and dc = 4 · 34∆ . (a) In the first step, we remove components of weak diameter less than 2dc . We can match the nodes in these component such that every node of degree at least ∆ − i + 1 in Gi is matched expect possibly nodes which were duplicated or one of their neighbors. This step takes O(dc ) rounds. (b) We now want to match the nodes left in higher diameter components. For this purpose in step 2, we select nodes in H such that the distance between two selected nodes in H is at least 2di in Gi and every node in H is at distance at most dc of a selected node as follows. We first construct H ′ , a subgraph of H from which we remove any node at distance less than 2di of a vertex of degree ∆ − i + 2 in Gi and from duplicated nodes in Gi . We then construct a clustering of the nodes in H ′ , which is described in BallCreation(H ′ , dc ). We let H ′′ be a copy of H ′ where we add an edge between two nodes if they are in different clusters and at distance less than 2di in Gi . The maximum degree in the graph H ′′ is at most ∆2di = ∆′ . We then apply the algorithm NodeSelection(H ′′ , C, dc /4, dc /2, ∆′ ) which returns one node for every cluster such that no two selected nodes are neighbors in H ′′ . (c) In step 3, we compute a matching in H using the selected nodes in the previous step. This matching is such that the only unmatched nodes are the selected nodes, the nodes of degree 3, or one their neighbors. Also, the distance between any two unmatched nodes is at least 2di . The matching is computed as follows. We first match nodes between the degree 3 nodes and the selected nodes such that all the nodes are matched except possibly the node of degree 3 or one of its neighbors and the selected node. Second, we match the nodes between the selected node such that only selected nodes and their neighbors can be unmatched. Lastly, we match the nodes which are just on one side of a selected node. If a selected node is left unmatched as well as one of its neighbor, we match them together. 5. We color every matched edge with color ∆ − i + 2 in Section 4.2.5. We show that the distance between every two nodes of degree ∆ − i + 1 or higher which are not matched is at least di .

4.2

One Phase of the Algorithm

In this section we study the phase i of the algorithm, and show the following. At the beginning of phase i, the graph Gi induced by uncolored edges is such that every node has a degree less or equal than ∆ − i + 2. The colors of the adjacent edges of every node node adjacent to uncolored edges are in the set {∆ − i + 3, ∆ + 1}. At the beginning of phase i + 1, the graph Gi+1 induced by uncolored edges is such that every node has a degree less or equal than ∆ − i + 1. The colors of the adjacent edges of every node node adjacent to uncolored edges are in the set {∆ − i + 2, ∆ + 1} . We let Gi be the graph induced by the uncolored edges in G. Gi is a bipartite graph in which every node has a degree less or equal to ∆ − i + 2. The distance between any two node of degree ∆ − i + 2 in Gi is at least di−1 . Notice that in phase 1, as there are no nodes of degree ∆ − i + 2 in G1 , we can choose whichever distance d0 we want as long as it is a function of ∆. 4.2.1

Removing and Coloring Connected Components of Diameter Less than 16di−1

Let us first look at the first step of the algorithm which consist of removing and coloring the connected component of small diameters. 28

Lemma 4.7. Every connected component of Gi of diameter less 16di−1 can be removed from Gi and colored in O(di−1 ) rounds. Proof. Every node collects its entire 16di−1 -hop neighborhood. After this, every node part of a connected component of diameter less than 16di−1 knows its entire component. Every node in this connected component has a degree equal or less than ∆ − i + 2 and is bipartite, so the edges in the component can be colored using colors from 1 to ∆ − i + 2 (Lemma 4.3). To do this, the node of maximum ID inside the component decides on the coloring of every edge and broadcast this information to every node in the component in 16di−1 rounds. 4.2.2

Constructing A (k, α, β)-net Modified Bipartite Double Cover

The next step is to construct a virtual graph on which we can use Theorem 3.6. The theorem requires the input graph to be bipartite, with a known bipartition, and to satisfy the (k, α, β)-net property, with α ≥ 3 and β ≥ 180. We first construct the bipartite double cover Gb = (X, Y, Eb ) of Gi and immediately remove from X all the nodes of degree strictly less than ∆−i+1. By construction, the bipartition of Gb is already known to the nodes. We now want to modify Gb to be (k, α, β)-net as described in Definition 2.2. The Properties 1 and 3 in the definition are satisfied for the parameters (∆ − i + 2, α, di−1 /α) as follows. Property 1 is satisfied as every node in X has degree at least ∆ − i + 1 and every node in Y has degree at most ∆ − i + 2. And Property 2 is satisfied as the (∆ − i + 2)-bad nodes are at distance di−1 since the bad nodes are only the nodes of degree ∆ − i + 2. In order to satisfy property 2, we need to create some ∆ − i + 2-good nodes. To achieve this, we first compute GU a subgraph of Gi composed of all the nodes at distance less 16dd of a node of degree ∆ − i + 2, as duplicated nodes need to be at distance at least di of nodes of degree ∆ − i + 2. We then compute an MIS S in (Gi \ GU )8dd . Then, every node u ∈ S picks arbitrarily one node at distance 2dd + 1 of u in Gi and add it to S, which is needed in order to ensure that every node in Y is at distance at most 4dd of a good node. Finally, we duplicate the Y copies of the nodes in S. We now prove some intermediate lemma which will be helpful for the next sections. Lemma 4.8. let S be the the set of selected nodes. the following properties are satisfied: 1. The distance between every two nodes in S is at least 2dd in Gi . 2. Every node in S is at distance at least 2dd from every node of degree ∆ − i + 2 in Gb . This step of duplicating nodes can be done in O(∆8dd log∗ n)-rounds Proof. Properties 1 and 2 are not useful to prove that Gb is (k, α, β)-net but will prove useful in the later subsections. Let GU be the subgraph containing all the nodes at distance less than 16dd of any node of degree ∆ − i + 2. The algorithm computes an MIS S on (Gi \ GU )8dd . Then, every node in S selects one node at distance 2dd + 1 in Gi and adds it to S. Only nodes in S are possibly duplicated. Property 1 is satisfied as the distance between every node in S is at least 2dd in Gi as follows. The distance between two MIS nodes is at least 8di and each MIS nodes select one node at distance 2dd + 1. The distance between any two selected nodes is at least 8dd − 2(2dd + 1) > 2dd . For property 2, we use here Lemma 4.2, which states that the bipartite double cover of a bipartite graph consist of two disjoint copies of that graph. This implies that if two nodes in Gi are at distance k then their copies are at distance k or are not connected. Since every node in S is at distance at least 2dd − 1 from a node of degree ∆ − i + 2 in Gi , it stands in Gb The complexity of creating S nodes is the complexity of computing the MIS on (Gi \ GU )8dd which is O(∆8dd log∗ n)-rounds. 29

We now prove the lemma which shows that Gb satisfy Property 2 in Definition 2.2 which we need to show that Gb is (k, α, β)-net. In that setting, one issue can arise when a node of degree ∆ − i + 2 has one neighbor of degree strictly less than ∆ − i + 1 Lemma 4.9. Every node in Y is at distance at most 64dd of a good node and if a node v of degree ∆ − i + 2 has a neighbor of degree strictly less than ∆ − i + 1, then vY adds a node to S at distance 2dd or it is in a connected component of diameter less or equal than 4dd in Gb Proof. Let v a node in Gi and vY ∈ Y its copy in Gb . v is at distance at most 40dd of a node s in S. If the distance between vY and sY is even, then vY and sY are in the same component in the original double cover of Gi . If not, then the node selected by s, s′ , at distance 2dd + 1 of s, is at even distance of v. Then s′ and v are in the same component. To summarize, vY is at distance at most 64dd of a node in S. Let u be that node. And let p = (v, v2 , ...v2k , u) be the shortest path between v and u in Gi . If the path p = (vY , v2,X , ...v2k,X , uY ) exists in Gb , it implies that v2k,X didn’t get removed from X and had degree ∆ − i + 1. After making the copy of uY , v2k,X now has a degree of ∆ − i + 2 and is a ∆ − i + 2-good node. In that case, v is at distance at most 64dd of a good node. If this path does not exist in Gb , it implies that there exist 1 ≤ j ≤ k, such that v2j,X got removed. But then the degree of v2j−1,Y got reduced by 1. If v2j−1,Y is not a node of degree ∆ − i + 2 in Gi , then v2j−1,Y is a ∆ − i + 2-good node in Gb . Let’s look at what happens if v2j−1,Y is a node of degree ∆−i+2 in Gi . If v2j−1 had two neighbors of degree strictly less than ∆−i+2, it is now a good node. In both cases, vY is then at distance at most 64dd good node. If v2j−1,Y doesn’t have two neighbors with degree strictly less than ∆ − i + 2, we do the following. v2j−1,Y finds one node at distance 2dd in Gb and adds it to S. This node verifies the properties of Lemma 4.8 and v is at distance less than 40dd + 16dd of that node. If v2j−1,Y cannot find such a node, it means that the connected component containing v2j−1,Y in Gb is of diameter less than 4dd . This component doesn’t contain any bad node, so a perfect matching exist in that component. Then, v2j−1,Y decides arbitrarily on a perfect matching for every node of the component, and we remove all of the nodes of the component from Gb . Lemma 4.10. After the duplication step, Gb becomes (∆ − i + 2, 64dd , di−1 /64dd )-net (Definition 2.2). Proof. The three properties that Gb needs to satisfy for being (∆ − i + 2, 64dd , di−1 /64dd )-net are described here Definition 2.2. Property 1 is satisfied as the minimum degree of X is ∆ − i + 1 and the degree of any node in Y is at most ∆ − i + 2. Property 3 is satisfied as the distance between every bad node is at least di−1 in Gi . Property 2 is also satisfied thanks to Lemma 4.9. 4.2.3

Constructing a Virtual Graph From The X-Saturated Matching

The algorithm compute an X-saturated matching Mi of Gb and uses it to construct a directed subgraph H = (V, E(H)) of Gi as following. The set of nodes of H is the same as the set of nodes of Gi . For every node edge (uX , vY ) ∈ Mi , we construct an edge (u, v) in H. This edge is oriented from u to v. There is one exception when there is both the edges (uX , vY ) and (vX , uY ) are in Mi . In that case, we only construct one edge. If u is a node which got duplicated, the nodes oriented edge from u to v in H. Similarly form v to u if v got duplicated. If neither v or u got duplicated, then the nodes orient the edge arbitrarily. Observation 4.11. The graph H constructed from the X-saturated matching of Gb is a directed graph with the following properties. 30

1. Every node of has degree at most 3 2. The distance between nodes of degree 3 in Gi is at least 2dd . 3. Nodes with degree strictly less than ∆ − i + 1 in Gi are of degree 1 or 0 unless the nodes are duplicated nodes. 4. Every node of degree 2 which wasn’t duplicated has one outgoing and one incoming edge. H is constructed in O(f (∆) log n) rounds. Proof. Consider G = (V, E) and Gb = (X, Y, Eb ) the bipartite double cover of Gi . The X-saturated matching is such that every node in X grabs a node in Y , and that every node in Y can be grabbed at most one, except the duplicated nodes which can be grabbed twice. We first prove property 1. For every node v ∈ V , there is vX ∈ X, vY ∈ Y and possibly vY′ ∈ Y if v is a duplicated node. The X-saturated matching ensures that vY and vY′ are grabbed at most once. And vX grabs only one node. Thus the degree of v is at most 3. We now prove property 2. To have degree 3, a node v needs to have been duplicated as non-duplicated node have degree at most 2. Since the distance between any two duplicated nodes is at least 2dd in Gi by construction, the distance between degree 3 nodes in Gi is at least 2dd . Properties 3 and 4 come down from how the saturated matching was performed and how H was constructed. For property 3, nodes of degree strictly less than ∆ − i + 1 are only contained in Y . Which means that their degree in H is equal to 1 or 0 if they didn’t get duplicated. For property 4, we know that every node of degree 2 which wasn’t duplicated has a degree equal or higher than ∆ − i + 1 in Gi . Their in X got matched to a neighboring node, which gave the node an outgoing edge. And since very node can only grab once, the other edge is an incoming edge. To construct H, the algorithm applies Theorem 3.6 which takes O(kα∆3α+2 log n + βα) rounds for k = ∆−i+2, α = 16dd and β = di−1 /16dd , which we can simplify as O(f (∆)·log n) rounds. 4.2.4

Almost Perfect Matching Via Node Selection

The algorithm now uses the graph H to find a matching of the nodes. However we cannot ensure that every node in H can be matched, since we want our round complexity to be in O(f (∆) log n) rounds. But we want every node that which does not get matched to be at distance at least di any other unmatched node, as this is the invariant we want to maintain. Lemma 4.12. SparseNodeSelection(Gi , H, di , ∆) ensures that nodes which will not be matched during phase i are of degree strictly less than ∆ − i + 1, or are of degree ∆ − i + 1 and at distance a least di between themselves and at distance di of any node of degree ∆ − i + 2 in Gi . This algorithm proceeds in O(f (∆) · log n) rounds. ′

We obtain this in three steps. But first, let ∆′ = ∆2di and dc = 4 · 34∆ . Notice that dd = ′ 16 · 34∆ = 4dc In the first step, we remove paths and cycles of weak diameter less than 2dc . We can match the nodes in these component such that every node of degree at least ∆ − i + 1 in Gi is matched expect possibly nodes or neighbor of nodes which were duplicated. This step takes O(dc ) rounds. Lemma 4.13. For every path or cycles of weak diameter at most 2dc , the algorithms computes a matching such that every unmatched node is of degree strictly less than ∆ − i + 1 or a duplicated node or a neighbor of a duplicated node. This step is done in O(dc )

31

Proof. First every node collects its 2dc -hop neighborhood in H. Then the node of highest ID on paths or cycle of weak-diameter less than 2dc decide arbitrarily on a matching and broadcast it to every nodes in the component. Several cases arise depending on the component. For component which are path with even number of nodes or cycles, there is a matching which matches every node of the component. Another type of component are paths with an odd number of nodes. We first consider the case where no node was duplicated on this path. In that case, this path p = (u1 , ..., uk ) is completely directed, starting from u1 and finishing in uk . Since uk has no outgoing edge and p contains no duplicated nodes, it can only be a node of degree strictly less than ∆ − i + 1 in Gi . If the path contains a node which was duplicated, we do the following. Let p = (u1 , ..., us , ...., uk ) the path we consider with us a duplicated node. We match the nodes starting from the extremity of the path until we reach the neighbors of us as follows. First match u1 to u2 ,... until we either match us−3 to us−2 or us−2 to us−1 . We do the same for the other extremity of the path. Once this matching is done, every node is matched except us and possibly us−1 and us+1 . If us−1 and us+1 are both matched, then us is the only node unmatched. If us−1 or us+1 or both are unmatched, us matches with one arbitrarily and at most one of us−1 and us+1 is unmatched. they get matched. We also match parts of the components containing nodes of degree 3. Let v be such a node. If there is a path p = (v, u1 , ..., uk ) or a cycle c = (v, ..., uk , v) of weak diameter less than 2dc , we match them as follows. Every cycle is matched perfectly if there is one. If the path is oriented from v towards uk , then we match nodes from u1 to wards uk . Since the distance between two duplicated nodes is at least dd > 8dc , uk is a node of degree strictly less than ∆ − i + 1 in Gi and so can be left unmatched. If the path is oriented from uk towards v, then we match nodes from uk to wards v such that every node on the path is matched except possibly v. Notice that matching these two paths can be done independently, and might only leave v as unmatched node. Since every component has weak diameter at most 2dc , this steps can be done in O(dc ) rounds. We now want to match the nodes left in components of diameter higher than 2dc . For this purpose in step 2, we select nodes in H such that the distance between two selected nodes in H is at least 2di in Gi and every node in H is at distance at most dc of a selected node as follows. We first construct graph H ′ a subgraph of H from which we remove any node at distance less than 2di of a vertex of degree ∆ − i + 2 in Gi and from duplicated nodes in Gi . We then construct a clustering of the nodes in H ′ , which is described in BallCreation(H ′ , dc ). We let H ′′ be a copy of H ′ where we add an edge between two nodes if they are in different clusters and at distance less than 2di in Gi . The maximum degree in the graph H ′′ is at most ∆2di = ∆′ . We then apply the algorithm NodeSelection(H ′′ , C, dc /4, dc /2, ∆′ ) which returns one node for every cluster such that no two selected nodes are neighbors in H ′′ . Lemma 4.14. In step 2, the algorithm constructs clusters and then selects nodes in each cluster such that, 1. the distance between selected nodes and nodes of degree ∆ − i + 2 is at least 2di in Gi , 2. the distance between two selected nodes is at least 2di in Gi , and 3. any node is at distance at most 23 dc of a selected node in H. Step 2 can be performed in O(f (∆) log n) rounds. Proof. We now are left with nodes on component of weak-diameter at least 2dc . We now want to select nodes which we will use in order to obtain an almost perfect matching. Since we don’t want 32

these nodes to be close to a node of degree ∆ − i + 2 in Gi , we first compute H ′ , a subgraph of H obtained by removing every vertex at distance at most 2di from a vertex of degree ∆ − i + 2 in Gi and from duplicated nodes in Gi . Now we want to create clusters of sufficiently large size to apply NodeSelection. To achieve this, we compute an MIS in the power graph H ′dc in O(dc + log∗ n) = O(f (∆) + log∗ n) rounds. We now go back to the graph H, and consider the MIS nodes in H ′ as MIS nodes in H. For each node v in the MIS, we create a cluster Cv containing all of the nodes at distance less then dc /4 of v in H ′ , so every cluster Cv has a diameter at least dc /4 and at most dc /2 since every component is of size at least 2dc . Since the MIS vertices are at at distance greater than dc , these clusters are pairwise disjoint. Let C be the set containing all the clusters. We let H ′′ be a copy of H ′ where we add an edge between two nodes if they are in different clusters and at distance less than 2di in ′ Gi . The maximum degree in the graph H ′′ is at most ∆2di = ∆′ . Since dc /4 ≥ 34∆ , we can apply NodeSelection(H ′′ , C, dc /4, dc /2, ∆) which selects exactly one vertex from each cluster such that the properties in Lemma 4.6 are respected. This takes at most O(f (∆) log n) rounds. First we show property 1, which states all selected node are at distance greater than 2di from nodes of degree ∆−i+2 in Gi and nodes of degree 3 as follows. Every selected node is at distance at most dc /4 of an MIS node. Or MIS nodes are at distance at least dc of a node of degree ∆−i+2 in Gi ′ and nodes of degree 3. So selected nodes are at distance at least 3dc /4 = 8∆′2 ·3∆ > ∆′ = ∆di > 2di . Property 2 is also satisfied as follows. NodeSelection(H ′′ , C, dc /4, dc /2, ∆) makes sure that the distance between selected node is at least 2 in H ′′ , so the distance between selected nodes in Gi is at least 2di . Property 3 is also satisfied as every node in H is at most di + dc of an MIS node, and any selected node is at distance at most dc /4 of an MIS node. In step 3, we compute a matching in H using the selected nodes in the previous step. This matching is such that the only unmatched nodes are the selected nodes, the nodes of degree 3, or one their neighbors. Also, the distance between any two unmatched nodes is at least 2di . Lemma 4.15. Step 3 matches every remaining node in H such that the distance between any two unmatched node is at least di . Step 3 can be done in O(dc ) rounds. Proof. We now compute a matching in H. We first match the neighborhood of nodes of degree 3. Since v does not have any component of diameter less than 2dc , there are at least 3 selected in its 3/2dc -hop neighborhood in H. We do the following matching. Let vk a selected node and let p = (v, v1 , ..., vk ) the path from v to node vk such that no vj is a selected node. We match every node starting from v1 up to vk or vk−1 . We now match the vertices on the remaining components. In each component, every selected vertex identifies the closest two selected vertex on either side, if they exist. For each pair s and s′ of consecutive selected vertices, we computes a matching covering all vertices between them leaving unmatched only the selected vertices and possibly their immediate neighbors as follows. Let p = (s, s1 , ...., sk , s′ ) the path between s and s′ . Let s be the node of highest ID between s and s′ . Then s matches every node starting from s1 up to sk or s′ . Lastly, we match the nodes which are just on one side of a selected node. Let p = (s, s1 , ...., sk ) with s a selected node. We start the matching from sk up to s1 or s2 . Finally, every selected vertex is matched whenever one of its neighbors is still available as follows. Let s a selected node and s1 and s2 its neighbors. If s1 or s2 are left unmatched, s matches with on arbitrarily. Doing all of these matching can be done in O(dc ) rounds. Consequently, the remaining unmatched node in H are selected node, duplicated nodes, or neighbors of one of these vertices. In particular, any two unmatched vertices are at distance at 33

least di as the distance between any of any two selected node is at least 2di . Any of these step takes O(dc ) rounds. We now prove Lemma 4.12 Proof. The combination of Lemma 4.13, Lemma 4.14 and Lemma 4.15 ensures that every node of degree ∆ − i + 1 in Gi or more is matched except some nodes which at distance at least di between themselves as follows. Lemma 4.13 ensures that every node of degree ∆ − i + 1 which is not matched and in a component of size less than 2dc is nodes which was duplicated or is a neighbor of a duplicated node. Lemma 4.13 ensures that every node of degree ∆ − i + 1 which is not matched in a component of size greater 2dc is either a node was which duplicated or a selected nodes, or or a neighbor of one of these two types of nodes. The distance between any two duplicated nodes is at least 2dd > 2di . The distance between any two selected nodes is at least 2di . The distance between a selected node and an unmatched duplicated node or an unmatched neighbor of a duplicated node is at least 2di . And the distance between selected nodes and nodes of degree ∆ − i + 2 is at least 2di . So the distance between any two unmatched node is at least di . The overall computation is O(f (∆) log n). 4.2.5

Proof of The Main Lemma

Lemma 4.16. In phase i, the algorithm and colors the edges between matched nodes with color ∆ − i + 2. The distance between any two nodes of degree ∆ − i + 1 after this step is di . Proof. Every edge in the matching gets color ∆ − i + 2. Lemma 4.12 shows that the distance between two nodes of degree ∆ − i + 1 which don’t get any edge colored is at least di and that every node of degree ∆ − i + 2 gets an edge colored as the only unmatched nodes are at distance at most one of a selected node or a duplicated node, and neither are node of degree ∆ − i + 2. So, every node in the graph Gi+1 has a degree of at most ∆ − i + 1.

4.3

Proof of the Main Theorem

We prove in this section, that Algorithm 1 outputs a proper ∆ + 1 edge coloring. Lemma 4.17. Let G be a graph of maximum degree 3 in which the nodes of degree 3 are pairwise at distance at least 5. Then a proper 3-edge-coloring of G can be computed in O(log∗ n) rounds. Proof. Partition the edges into three classes: EA , the edges incident to a node of degree 3; EB , the edges of E \ EA adjacent to no edge of EA ; and EC = E \ (EA ∪ EB ). Coloring EA . Every node of degree 3 properly colors its three incident edges with the three distinct colors 1, 2, 3. Since degree-3 nodes are pairwise at distance at least 3, two such stars are edge-disjoint and contain no pair of adjacent edges, so no conflict arises. This takes O(1) rounds. Coloring EB . Both endpoints of an edge in EB have degree at most 2, and by definition no adjacent edge lies in EA . Hence the subgraph (V, EB ) is a disjoint union of paths and cycles, and its line graph again consists of paths and cycles, which can be properly 3-colored in O(log∗ n) rounds [30]. Edges of EC are still uncolored at this point, so they impose no constraint. Coloring EC . An edge of EC has both endpoints of degree at most 2 and is thus adjacent to at most two edges, so at most two colors are forbidden and a color in {1, 2, 3} remains. Moreover, no two edges of EC are adjacent: each edge of EC is adjacent to an edge of EA , so two adjacent edges of EC would place two degree-3 nodes at distance at most 4, contradicting the assumption. Hence all edges of EC can be colored greedily and simultaneously in O(1) rounds. 34

We now prove the main theorem which we restate for convenience. Theorem 1.1. There exists a function f such that, on bipartite graphs, a (∆ + 1)-edge coloring can be computed deterministically in O(f (∆) log n) rounds. This holds even when the bipartition is not known to the vertices. d

Proof. We have (di ) such that d∆−2 = 100 and for all ∆ − 2 ≥ i ≥ 1, di−1 = 16 · 11520 · 34∆ i . After ∆ − 2 phases, all edges expect the edges of G∆−1 are colored with a color in (4, ∆ + 1). the maximum degree of the nodes in G∆−1 is at most 3 and all of the nodes of degree 3 are at distance d∆−2 = 100 between each other. This graph G∆−1 can be colored using color in {1, 2, 3} (Lemma 4.17). We prove additionally the local version of the theorem. Theorem 1.3. On bipartite graphs (even without the bipartition being known to the vertices), a (∆ + 1)-edge coloring where each edge {u, v} receives a color from {1, . . . , max(deg(u), deg(v)) + 1} can be computed deterministically in O(f (∆) log n) rounds, for some function f . Proof. The coloring we have obtained is already satisfying these properties. Indeed, in step i, every edge colored using the matching has one of its endpoint of degree ∆ − i + 1. However some edges where colored in small component independently (Lemma 4.3). These edges are also colored properly as every bipartite graph can be edge-colored such that every edge e = (u, v) has a color in {1, max(deg(u), deg(v))}

4.4

Node Selection

We prove Lemma 4.6 in this subsection. Algorithm 4 NodeSelection(G, C, dmax , ∆) 1: Compute a 2∆ − 1 edge coloring in G 2: Let S = V be the set of choosable nodes 3: for i = 1 to 2∆ − 1 do 4: Let Gi the graph induced by the edges of color i in G and the nodes in S 5: Group nodes in Gi which are in the same cluster in groups of 3 6: Let Hi an empty graph and for each group in Gi , add a node to Hi 7: Add an edge e′ = (u′ , v ′ ) in Hi if u′ and v ′ contain two nodes which are adjacent 8: Apply sinkless orientation on Hi 9: Remove from S every node with an incoming edge 10: Output for each cluster a node with only outgoing edges. Let G be a bipartite graph of maximum degree ∆ and C a clustering of nodes of the graph with minimum diameter dmin and maximum diameter dmax . We want every cluster to select one node such that no neighbor of that node is selected by another cluster. In order to obtain this, at a high level, we remove nodes from every cluster in a succession of phases. At the end of all phases, every cluster should be left with a small number of nodes such that no neighbors of these nodes are still contained in a cluster. Initially, the algorithm colors the edges of the graph G with 2∆ − 1 colors which takes O(∆ + ∗ log n) rounds. We now do 2∆ − 1 phases from i = 1 to 2∆ − 1. Let i be the current phase and let Gi be the graph induced by the edges of color i. From each graph Gi , we construct a virtual graph Hi . In each graph Gi , inside each cluster C ∈ C, we group 35

nodes in groups of 3 expect possibly one node of degree less than 3 and create one node for each of these groups in Hi . For every node created in Hi , there is an edge between two nodes vi′ and u′i if one of the nodes in vi′ is neighbor to a node in u′i . Then we compute a sinkless orientation on Hi . Every node in Hi has then one outgoing edge if it was a node of degree 3. By choosing dmin sufficiently large compared to ∆, we can ensure that every cluster has one node with only outgoing edges. We say a node is choosable if it has no incoming edge. We let S be the set of choosable nodes. Initially, all nodes in a cluster are choosable, so S = V . Observation 4.18. Let si be the minimum number of choosable nodes in each cluster C at the beginning of phase i. Then si+1 ≥ ⌊si /3⌋ − 2. Each phase i can be done in at most O(dmax log n). Proof. Lets assume we are in phase i. Let Gi be the subgraph of G induced by the edges of color i and the nodes in S. Let si be the minimum number of choosable nodes in each cluster C at the beginning of phase i. We first construct a virtual graph Hi . For each cluster C ∈ C, C groups arbitrarily the choosable nodes inside it, which have an edge with color i, in groups of 3 and creates a node in Hi for every group. Doing this grouping can be done in 2dmax rounds, as every cluster can appoint the node of highest ID inside the cluster as a leader and have it decide the grouping arbitrarily. Since the size of Hi is not a multiple of 3, one group could be of size 2 or 1. Hi is the following graph: Every node in Hi has degree at most 3 and represent a group of nodes, all inside the same cluster. Since we want to simulate the sinkless orientation algorithm, we remove from Hi the nodes of degree strictly less than 3 and create a half edge for each edge removed which had an endpoint of degree 3. Each node in Hi , gets for ID, the ID of the node of highest ID in its group. Now the algorithm simulates computation of sinkless orientation in the graph Hi (Lemma 4.4), which is possible as every node in Hi now has a degree of exactly 3. The simulation of sinkless orientation in Hi can take up to O(dmax log n) rounds as the distance between any two neighbors in Hi is at most dmax in G. Every node in Hi with degree 3 has at least one outgoing edge. So, every node in Hi with degree 3 contains one node which remains choosable. Lets at a cluster C ∈ C. In the beginning of phase i, the number of choosable nodes was si . A node went from being choosable to not-choosable if it had an edge oriented as incoming during the sinkless orientation computation. The number of nodes in Hi which were in C was at most ⌊si /3⌋ + 2. And every one of these nodes, if they had degree 3 had an outgoing edge. So at most 2⌊si /3⌋ + 2 of the nodes in C go from choosable to non choosable. Which means that number of choosable nodes in B has decrease to at least si − (2⌊si /3⌋ + 2) = ⌊si /3⌋ − 2. We now prove the main lemma. Lemma 4.6. [Node Selection] Let G a graph of maximum degree ∆ and C a partition of the nodes of the graph into subset of nodes such that every b ∈ C has diameter at least dmin ≥ 34∆ . The NodeSelection(G, C, dmax , ∆) algorithm returns a subset P of the nodes in G such that, 1. At Most One Node Per Cluster: There is no C ∈ C and vp , up ∈ P , such that vp ∈ C,and up ∈ C 2. At Least One Node Per Cluster: For every C ∈ C, there exists vp ∈ P , such that vp ∈ C. 3. No Neighboring Selected Nodes: For every vp , up ∈ P , dG (vp , up ) ≥ 2 The round complexity of NodeSelection(G, C, dmax , ∆) is O(∆ · dmax · log n)

36

Proof. We have dmin ≥ 34∆ . We obtain the result by the following induction, that si ≥ 34∆+2−2i . This is true for step 1 as s1 ≥ dmin . Let assume this is correct until step i. Then, by Observation 4.18, si+1 ≥ ⌊si /3⌋ − 2 ≥ ⌊34∆−2i /3⌋ − 2 = 34∆−2i−1 − 2 ≥ 34∆−2i−2 . After the 2∆ − 1 phases, the number of choosable nodes is d2∆ = 32 = 9. The overall algorithm has a round complexity of O(∆dmax log n).

Acknowledgements All results were obtained by the authors without the use of AI. For the write-up, GPT-5.5 and Claude Opus 4.8 have partially been used for literature review and language editing and have assisted in drafting preliminary versions of technical and related-work sections. All generated content has been carefully checked and modified by the authors. The authors assume responsibility for all content. Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. This work is supported by ERC grant OLA-TOPSENS (grant agreement number 101162747) under the Horizon Europe funding programme.

References [1]

Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. “Distributed approximate maximum matching in the CONGEST model”. In: 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. 2018, pp. 6–1.

[2]

Sepehr Assadi. “Faster Vizing and near-Vizing edge coloring algorithms”. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2025, pp. 4861–4898.

[3]

Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martı́n Costa, Shay Solomon, and Tianyi Zhang. “Vizing’s Theorem in Deterministic Almost-Linear Time”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2026, pp. 5558–5585.

[4]

Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martı́n Costa, Shay Solomon, and Tianyi Zhang. “Vizing’s theorem in near-linear time”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025, pp. 24–35.

[5]

Alkida Balliu, Thomas Boudier, Francesco d’Amore, Fabian Kuhn, Dennis Olivetti, Gustav Schmid, and Jukka Suomela. “Distributed Algorithms for Potential Problems”. In: Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing. 2026.

[6]

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. “Distributed edge coloring in time polylogarithmic in ∆”. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. 2022, pp. 15–25.

[7]

Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. “Almost global problems in the LOCAL model”. In: Distributed Computing 34.4 (2021), pp. 259–281.

[8]

Alkida Balliu, Filippo Casagrande, Francesco d’Amore, and Dennis Olivetti. “New Hardness Results for the LOCAL Model via a Simple Self-Reduction”. In: Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing. 2026. 37

[9]

Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. “Node and edge averaged complexities of local graph problems”. In: Distributed Comput. 36.4 (2023), pp. 451–473. doi: 10.1007/S00446-023-00453-1.

[10]

Alkida Balliu, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. “New classes of distributed time complexity”. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018, pp. 1307–1318.

[11]

Anton Bernshteyn. “A fast distributed algorithm for (∆ + 1)-edge-coloring”. In: Journal of Combinatorial Theory, Series B 152 (2022), pp. 319–352.

[12]

Anton Bernshteyn and Abhishek Dhawan. “Fast algorithms for Vizing’s theorem on bounded degree graphs”. In: J. Comb. Theory B 175 (2025), pp. 69–125. doi: 10.1016/J.JCTB.2025. 07.002.

[13]

Sayan Bhattacharya, Din Carmon, Martı́n Costa, Shay Solomon, and Tianyi Zhang. “Faster √ (∆ + 1)-Edge Coloring: Breaking the m n Time Barrier”. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2024, pp. 2186–2201.

[14]

Sayan Bhattacharya, Martı́n Costa, Nadav Panski, and Shay Solomon. “Nibbling at long cycles: Dynamic (and static) edge coloring in optimal time”. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2024, pp. 3393– 3440.

[15]

Sayan Bhattacharya, Martı́n Costa, Shay Solomon, and Tianyi Zhang. “Even faster (∆ + 1)edge coloring via shorter multi-step Vizing chains”. In: Proceedings of the 2025 Annual ACMSIAM Symposium on Discrete Algorithms (SODA). SIAM. 2025, pp. 4914–4947.

[16]

Joakim Blikstad, Yannic Maus, and Tijn de Vos. “Deterministic Edge Coloring with few Colors in CONGEST”. In: arXiv preprint arXiv:2603.02689 (2026).

[17]

Oleg V Borodin, Alexandr V Kostochka, and Douglas R Woodall. “List edge and list total colourings of multigraphs”. In: Journal of combinatorial theory, Series B 71.2 (1997), pp. 184– 204.

[18]

Oleg V. Borodin, Alexandr V. Kostochka, and Douglas R. Woodall. “List Edge and List Total Colourings of Multigraphs”. In: J. Comb. Theory B 71.2 (1997), pp. 184–204. doi: 10.1006/JCTB.1997.1780.

[19]

Yann Bourreau, Sebastian Brandt, and Alexandre Nolin. “Faster Distributed ∆-Coloring via a Reduction to MIS”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2026, pp. 4481–4500.

[20]

Yann Bourreau, Sebastian Brandt, and Alexandre Nolin. “Faster distributed ∆-coloring via ruling subgraphs”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025, pp. 1307–1318.

[21]

Sebastian Brandt. “An automatic speedup theorem for distributed problems”. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 2019, pp. 379–388.

[22]

Sebastian Brandt, Yi-Jun Chang, Jan Grebı́k, Christoph Grunau, Václav Rozhon, and Zoltán Vidnyánszky. “Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics”. In: 13th Innovations in Theoretical Computer Science Conference, ITCS. Vol. 215. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 29:1–29:26. doi: 10.4230/LIPICS.ITCS.2022.29.

38

[23]

Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. “A lower bound for the distributed Lovász local lemma”. In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016, pp. 479–488.

[24]

Sebastian Brandt, Yannic Maus, Ananth Narayanan, Florian Schager, and Jara Uitto. “On the locality of Hall’s theorem”. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2025, pp. 4198–4226.

[25]

Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. “Distributed edge coloring and a special case of the constructive Lovász local lemma”. In: ACM Transactions on Algorithms (TALG) 16.1 (2019), pp. 1–51.

[26]

Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. “An exponential separation between randomized and deterministic complexity in the LOCAL model”. In: SIAM Journal on Computing 48.1 (2019), pp. 122–143.

[27]

Yi-Jun Chang and Seth Pettie. “A time hierarchy theorem for the LOCAL model”. In: SIAM Journal on Computing 48.1 (2019), pp. 33–69.

[28]

Aleksander BG Christiansen. “Deterministic Dynamic Edge Colouring”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2026, pp. 1047–1096.

[29]

Aleksander Bjørn Grodt Christiansen. “The power of multi-step Vizing chains”. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023, pp. 1013–1026.

[30]

Richard Cole and Uzi Vishkin. “Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking”. In: Information and Control 70.1 (1986), pp. 32–53.

[31]

Manuela Fischer. “Improved deterministic distributed matching via rounding”. In: Distributed Computing 33.3-4 (2020), pp. 279–291.

[32]

Fred Galvin. “The list chromatic index of a bipartite multigraph”. In: Journal of Combinatorial Theory, Series B 63.1 (1995), pp. 153–158.

[33]

Mohsen Ghaffari and Christoph Grunau. “Near-optimal deterministic network decomposition and ruling set, and improved MIS”. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2024, pp. 2148–2179.

[34]

Mohsen Ghaffari and Fabian Kuhn. “Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition”. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2022, pp. 1009–1020.

[35]

Mohsen Ghaffari and Hsin-Hao Su. “Distributed Degree Splitting, Edge Coloring, and Orientations”. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete. SIAM, 2017, pp. 2505–2523. doi: 10.1137/1.9781611974782.166.

[36]

Christoph Grunau, Václav Rozhoň, and Sebastian Brandt. “The landscape of distributed complexities on trees and beyond”. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. 2022, pp. 37–47.

[37]

Philip Hall. “On Representatives of Subsets”. In: Classic Papers in Combinatorics. Springer, 1987, pp. 58–62.

[38]

Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. “On the Distributed Complexity of Computing Maximal Matchings”. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM/SIAM, 1998, pp. 219–225. 39

[39]

Manuel Jakob and Yannic Maus. “Towards optimal distributed ∆-coloring”. In: International Colloquium on Structural Information and Communication Complexity. Springer. 2026, pp. 391–410.

[40]

Manuel Jakob, Yannic Maus, and Florian Schager. “Towards Optimal Distributed Edge Coloring with Fewer Colors”. In: 39th International Symposium on Distributed Computing, DISC 2025. Vol. 356. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 37:1–37:26. doi: 10.4230/LIPICS.DISC.2025.37.

[41]

Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang. “On the Randomized Locality of Matching Problems in Regular Graphs”. In: 39th International Symposium on Distributed Computing, DISC 2025. Vol. 356. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 40:1–40:20. doi: 10.4230/LIPICS.DISC.2025.40.

[42]

Seri Khoury and Aaron Schild. “Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching”. In: 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025. IEEE, 2025, pp. 2292–2305. doi: 10.1109/FOCS63196.2025.00120.

[43]

D. König. “Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre”. ger. In: Mathematische Annalen 77 (1916), pp. 453–465. url: http : / / eudml . org / doc / 158740.

[44]

Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. “Local computation: Lower and upper bounds”. In: Journal of the ACM (JACM) 63.2 (2016), pp. 1–44.

[45]

Nathan Linial. “Locality in Distributed Graph Algorithms”. In: SIAM Journal on computing 21.1 (1992), pp. 193–201.

[46]

Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. “Improved distributed approximate matching”. In: Journal of the ACM (JACM) 62.5 (2015), pp. 1–17.

[47]

Andrew S Marks. “A determinacy approach to Borel combinatorics”. In: Journal of the American Mathematical Society 29.2 (2016), pp. 579–600.

[48]

Yannic Maus, Alexandre Nolin, and Florian Schager. “Fast Deterministic Distributed Degree Splitting”. In: arXiv preprint arXiv:2604.00724 (2026).

[49]

V. G. Vizing. “On an Estimate of the Chromatic Class of a p-Graph”. In: Diskret analiz 3 (1964), pp. 25–30.

40

Related documents

• Distributed $(Δ+1)$-Coloring in $O(\sqrtΔ+\log^* n)$ Rounds#1328165
• Distributed $(Δ+1)$-Coloring in $O(\sqrtΔ+\log^* n)$ Rounds#1318985
• Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling#1117362
• Almost Lossless Transfer for Cuttable Distributed Problems#1326846
• Greedy-Like Defective Coloring: Distributed Algorithms and Applications#999838