Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing

Introduction

Edge coloring is a classical and fundamental topic in graph theory and algorithms. We study the weighted edge coloring problem, where we are given an edge-weighted graph $G := (V, E)$, possibly with parallel edges but without loops, and a weight function $w : E \to(0, 1]$. A coloring is a proper weighted coloring if, at every vertex, the sum of the weights of incident edges of each color is at most one. The objective is to minimize the number of colors, denoted by $\chi'_{w}(G)$.

This problem is a generalization of classical edge coloring in unweighted graphs (when all edge weights are one) and bin packing (when the graph is a star). Apart from its structural importance, the problem also finds many applications in switching networks, scheduling, frequency assignment, and graph decomposition. A principal application is multirate routing in three-stage Clos networks [6, 28, 7]. Here, vertices represent input and output switches, edges represent unsplittable connection requests, and colors represent middle-stage switches. Minimizing the number of colors reduces the interconnection resources needed to support simultaneous requests in communication and parallel-computing systems. We refer to Correa and Goemans [5] for a detailed account of this connection.

In (unweighted) edge coloring, a color class forms a matching. Three classical theorems describe much of the landscape. Kőnig’s theorem gives $\chi'(G) = \Delta(G)$ for bipartite multigraphs [25]; Vizing’s theorem gives $\chi'(G) \le\Delta(G) + 1$ for simple graphs [36]; and Shannon’s theorem gives $\chi'(G) \le\lfloor3\Delta(G)/2 \rfloor$ for arbitrary multigraphs [34]. Here $\Delta(G)$ is the maximum vertex degree.

In the weighted setting, two natural local lower bounds are $\Delta_w(G) := \max_{v \in V} \sum_{e \ni v} w_e$, and $\operatorname{bp}(G) := \max_{v \in V} \operatorname{bp}_v(G)$, where $\operatorname{bp}_v(G)$ is the minimum number of unit-capacity bins needed to pack the weights of the edges incident with $v$. Every proper weighted coloring induces a feasible bin packing at each vertex, so $\lceil\Delta_w(G) \rceil\le\operatorname{bp}(G) \le\chi'_{w}(G)$. We call the ratio $\chi'_{w}(G)/\operatorname{bp}(G)$, when $\operatorname{bp}(G) > 0$, the global-to-local packing gap: it measures the additional cost of reconciling locally feasible packings into a single coloring. Even on a star, the distinction between volume and local packability matters. A star with $k$ edges of weight $1/2 + \varepsilon$ has $\chi'_{w}(G) = \operatorname{bp}(G) = k$ and $\Delta_w(G) = k(1/2 + \varepsilon)$. In particular, $\chi'_{w}(G) > 2\Delta_w(G) - 1$ whenever $0 < \varepsilon< 1/(2k)$.

In 1991, Chung and Ross [7] conjectured that every bipartite multigraph admits a proper weighted coloring using $2\operatorname{bp}(G) - 1$ colors.¹ Feige and Singh [15] also proposed a related conjecture that a proper weighted coloring exists using at most $2N - 1$ colors, where $N$ is the smallest integer strictly greater than $\Delta_w(G)$, namely $N = \lceil\Delta_w(G) \rceil+ 1$. These conjectures ask how efficiently locally feasible packings can be reconciled into a globally consistent coloring. The conjectures have motivated a sequence of works in approximation algorithms.

Du, Gao, Hwang, and Kim [8] obtained the bound $\chi'_{w}(G) \le\frac{41}{16}\operatorname{bp}(G) + O(1)$ for bipartite multigraphs. Correa and Goemans [5] improved this to $2.5480\operatorname{bp}(G) + o(\operatorname{bp}(G))$ and separately established $2.557\Delta_w(G) + o(\Delta_w(G))$. Feige and Singh [15] subsequently gave a combinatorial algorithm using $\lceil\frac{9}{4}\Delta_w(G) \rceil$ colors. Khan and Singh [24] gave a guarantee of $\lceil2.2223\operatorname{bp}(G) \rceil$ colors. Ngo and Vu [30] constructed bipartite instances exhibiting a $5/4$ gap between $\chi'_{w}(G)$ and $\operatorname{bp}(G)$.

For arbitrary multigraphs, Feige and Singh [15] extended their algorithm to use at most $\lceil\frac{9}{4}\Delta_w(G) \rceil+ \mu(G)$ colors, where $\mu(G)$ is the maximum edge multiplicity. Odd cycles and multiplicities create genuine obstructions. The triangle example recorded by Feige and Singh [15 Section 1.2] has $t$ parallel edges on each side, all of weight $1/2 + \varepsilon$. It has $\chi'_{w}(G) = 3t$, $\operatorname{bp}(G) = 2t$, and $\Delta_w(G) = t(1 + 2\varepsilon)$: its global-to-local packing gap is $3/2$, while its ratio to weighted degree approaches three. Improved bounds are also known for certain special graph classes; see Huc [21] and Sannyasi [32].

Despite this progress, even for simple bipartite graphs, it remained unknown whether the local bin-packing bound approximates the global optimum asymptotically, or whether the factor two in terms of maximum weighted degree is sufficient asymptotically. More broadly, weighted analogues of Vizing’s and Shannon’s theorems remained elusive.

Our contributions

We establish weighted analogues of Vizing’s, Kőnig’s, and Shannon’s theorems, resolve the Chung–Ross conjecture asymptotically, and disprove the exact weighted-degree conjecture of Feige and Singh. Our main results are summarized below.

The coefficient one for simple graphs and the total-weight coefficients two and three are optimal.²

In the following, we explain the results in more detail.

Simple graphs: an asymptotic weighted analogue of Vizing’s theorem. Our main result shows that $\chi_w(G) \le\operatorname{bp}(G) + o(\operatorname{bp}(G))$ for every simple graph, whether or not it is bipartite. This (asymptotically) extends the coefficient-one phenomenon of Vizing’s theorem to weighted graphs.

The local packing problems here are considerably richer than in the unweighted setting. When every edge has weight one, a local bin can contain only one edge. With arbitrary weights, an optimal local packing may rely on intricate combinations of different item sizes. Moreover, these packings cannot be chosen independently: an edge belongs to the packing problems at both of its endpoints and must receive the same color at both. Surprisingly, our result shows that these local packings can nevertheless be made globally consistent with an asymptotically vanishing relative loss.

The main technical contribution is a local-to-global rounding framework. Our rounding theorem coordinates the local choices while retaining almost all incident weight at every vertex. To coordinate local packing distributions, we use partial resampling [20, 29] and hypergraph matching [10]. The proof has four main steps. First, each local bin is represented by a short description consisting of a bounded number of slots for large edges and reserved space for small edges. Second, fractional assignments link compatible slots at the two endpoints of each edge. Third, we choose one description for each vertex and color, controlling the resulting local capacities. Finally, hypergraph matching selects whole large edges, and a separate rounding procedure assigns the small edges. A small fresh palette colors the remaining edges. A key feature is that the loss at every vertex is $o(\operatorname{bp}(G))$, independently of the number of vertices. See § 3 for details.

Tight weighted degree bounds and the Chung–Ross conjecture. For bipartite multigraphs we obtain an asymptotically tight guarantee: $\chi_w'(G) \le(2 + o(1))\Delta_w(G)$. In particular, since $\Delta_w(G) \le\operatorname{bp}(G)$, this establishes the Chung–Ross conjecture asymptotically.

The proof groups parallel edges into feasible bundles, leaving a simple graph of light remainders. Kőnig’s theorem properly colors the heavier bundles with approximately $2\Delta_w(G)$ colors. The challenge is that a remaining edge can use only a color missing at both endpoints, and the two sets of missing colors may initially have little overlap. Kempe-style exchanges along two-color paths coordinate these missing sets in a weighted average sense, after which the simple-graph local-to-global rounding theorem completes the coloring. Thus the bipartite bound is also a substantial application of our main rounding framework. See § 4 for details.

For arbitrary loopless multigraphs we obtain the tight bound $\chi_w'(G) \le3\lceil\Delta_w(G)\rceil$. This proof is considerably simpler and independent of the rounding machinery. We present a self-contained argument for this guarantee as a gentle starting point in § 2.

Improved bounds from the contents of bins. Exploiting local bin packing, we obtain further improvements on upper bounds on $\chi_w'(G)$: $(1.62 + o(1))\operatorname{bp}(G)$ for bipartite multigraphs, and $(1.999 + o(1))\operatorname{bp}(G)$ for arbitrary loopless multigraphs.

The bipartite bound builds on our rounding framework. We first use harmonic rounding, ubiquitous in bin packing [26], to achieve a guarantee of the classical harmonic constant $h_\infty\approx1.691$. The further improvement to 1.62 uses three selections of edges from compatible weight ranges: a heavy edge and a small edge, or two small edges, can share one color. Coloring these selections separately reduces the harmonic charge of the remainder.

For general multigraphs, packet coloring must additionally respect odd-set constraints. Degree bounds from the previous results already handle sufficiently large odd sets, so the difficult cases reduce to dense triangles and five-vertex sets. We show that the relevant obstructions can be selected disjointly and contracted. After coloring the remaining edges, we restore their internal edges without conflicting with external colors. For multigraphs, we also employ fractional edge-coloring methods [11, 35]. Finally, this gives a coefficient strictly below two even without bipartiteness; the details are explained in § 6.

Lower bounds and exact conjectures. We give a simple bipartite counterexample (see § 5.1) to the exact weighted-degree conjecture of Feige and Singh [15]: it has $\Delta_w(G) = 39/20 < 2$ but $\chi_w'(G) = 4$, whereas the conjecture predicts three colors.

Parallel edges make the simple-graph theorem genuinely special. We construct bipartite multigraphs $G_N$ with $\operatorname{bp}(G_N) = 3N$, $\chi_w'(G_N) = 4N$, although the underlying simple graph is a tree of maximum degree three (see § 5.2). This improves the earlier $5/4$ lower bound of [30] to $4/3$. Our bounds also show that the ratio of the optimal uniform asymptotic coefficients for general and bipartite multigraphs, relative to $\operatorname{bp}(G)$, is strictly less than $3/2$: $\frac{1.999}{4/3} < \frac{3}{2}$.

Algorithms and verification. All five upper bounds in Theorem 1.1 have polynomial-time algorithms. Their descriptions and running-time analyses appear in the appendices. Companion Lean 4 formalizations cover the five existence statements in the table, not the running-time analyses.

Related results.

Our algorithms draw on classical bin-packing ideas, including linear grouping [FdIVL81], configuration-LP and rounding [22, 19]. They also use techniques from online bin packing related to Harmonic grouping [26, 31, 33]. For recent developments on online bin packing, see [BBD⁺18, BBD⁺21, HKS24, ADKS25, DJKS26]. The online variant of weighted edge coloring, where edges must be colored irrevocably upon arrival, has also been studied [5, 12].

A Weighted Analogue of Shannon's Theorem

We begin with an elementary argument showing that every loopless weighted multigraph admits a coloring with $\chi'_w(G) \le3\lceil\Delta_w(G)\rceil$. Unlike our subsequent results, this argument requires no probabilistic rounding. Here, the idea is to properly color a carefully selected subgraph and then insert all remaining edges into the same palette. It is similar in spirit to the previous approaches of Feige and Singh [15]. See Section B for omitted details in this section.

Select and color a bounded-degree skeleton. Put $n = \lceil\Delta_w(G)\rceil$ and inspect the edges in nonincreasing order of weight. Starting with $F = \varnothing$, keep an edge if adding it leaves the degree of $F$ at most $2n$ at both endpoints. Thus $\Delta(F) \le2n$, and Shannon’s theorem properly colors $F$ with at most $3n$ colors. Pad the palette with unused colors to obtain exactly $3n$ colors. A constructive proof of the required form of Shannon’s theorem appears in Lemma B.1.

Consider a rejected edge $e = uv$ of weight $a$. When $e$ was inspected, one endpoint, say $u$, already had $2n$ selected edges. Each was inspected before $e$ and therefore has weight at least $a$. We call these edges the witnesses of $e$. The witnesses serve two purposes. First, $a < 1/2$: otherwise the $2n$ witnesses together with $e$ would have weight at least $(2n + 1)/2 > n$ at $u$, contradicting $\Delta_w(G) \le n$. Second, because the coloring of $F$ is proper, the witnesses receive $2n$ distinct colors. We never recolor $F$, so each of these colors continues to carry load at least $a$ at $u$, regardless of which other edges are inserted. The following elementary lemma explains why the witnesses suffice.

Proof sketch. Suppose, to the contrary, that no color has room at both endpoints. Then every color has load greater than $1-a$ at one endpoint. Let $S = \{c : y_c > 1-a\}$, and $s = |S|$. Since $\sum_c y_c \le n$, we have $s < n/(1-a)$; for every $c \notin S$, we must have $x_c > 1-a$.