betaFeedback

WorksMathematics

The Brualdi–Quinn conjecture on strong edge-coloring holds fractionally and asymptotically

Abstract

Let GG be a bipartite graph with parts AA and BB, and let ΔAΔ_A and ΔBΔ_B be the maximum degrees of the vertices in AA and in BB, respectively. Brualdi and Quinn conjectured that the strong chromatic index of GG is at most ΔAΔBΔ_AΔ_B. We prove that the fractional strong chromatic index of GG is at most ΔAΔBΔ_AΔ_B, and that the conjecture holds asymptotically: χs′(G)≤(1+o(1))ΔAΔBχ_s'(G)\le(1+o(1))Δ_AΔ_B as max⁡{ΔA,ΔB}→∞\max\{Δ_A,Δ_B\}\to\infty. The error term is 12(ln⁡Δ)1/2Δ−1/412(\lnΔ)^{1/2}Δ^{-1/4} with Δ=max⁡{ΔA,ΔB}Δ=\max\{Δ_A,Δ_B\}. Both results rest on a smart partition of edges and Lovász Local Lemma.

Introduction

All graphs in this paper are finite and simple. A strong edge-coloring of a graph GG is an assignment of colors to the edges of GG in which every color class is an induced matching; equivalently, two edges receive distinct colors whenever they share an endpoint or are joined by an edge. The strong chromatic index χs′(G)\chi'_s(G) is the minimum number of colors in a strong edge-coloring of GG. The notion was introduced by Fouquet and Jolivet [11]. For a graph of maximum degree Δ\Delta, a greedy argument gives χs′(G)≤2Δ2−2Δ+1\chi'_s(G) \le2\Delta^2-2\Delta+1. Erdős and Nešetřil [8] conjectured that

χs′(G)≤{54Δ2,if Δ is even,14(5Δ2−2Δ+1),if Δ is odd.\chi'_s(G) \le \begin{cases} \frac{5}{4}\Delta^2, & \text{if }\Delta\text{ is even},\\ \frac{1}{4}(5\Delta^2-2\Delta+1), & \text{if }\Delta\text{ is odd}. \end{cases}

Molloy and Reed [16] established the first asymptotic improvement over the greedy bound on χs′(G)\chi'_s(G) where they proved that χs′(G)≤1.998Δ2\chi'_s(G) \le1.998\Delta^2 for sufficiently large Δ\Delta. This was successively improved to 1.93Δ21.93\Delta^2 by Bruhn and Joos [4], to 1.835Δ21.835\Delta^2 by Bonamy, Perrett and Postle [2], and to 1.772Δ21.772\Delta^2 by Hurley, de Joannis de Verclos and Kang [14]. More recently, Davey, Hurley, de Joannis de Verclos, Kang and Volec [6] obtained the bound 1.73Δ21.73\Delta^2 by way of flag algebra.

For bipartite graphs, Faudree, Gyárfás, Schelp and Tuza [9] proposed the following conjecture.

Conjecture 1 (Faudree, Gyárfás, Schelp and Tuza [9]). Every bipartite graph GG with maximum degree Δ(G)\Delta(G) satisfies χs′(G)≤Δ(G)2\chi'_s(G) \le\Delta(G)^2.

Brualdi and Quinn [3] proposed a stronger, asymmetric version. Let GG be bipartite with parts AA and BB, and let

ΔA=max⁡x∈Ad(x),ΔB=max⁡b∈Bd(b).\Delta_A=\max_{x\in A}d(x),\qquad\Delta_B=\max_{b\in B}d(b).

Conjecture 2 (Brualdi and Quinn [3]). Every bipartite graph GG satisfies χs′(G)≤ΔAΔB\chi'_s(G) \le\Delta_A\Delta_B.

Both conjectures are tight: if ∣A∣=ΔB|A| = \Delta_B and ∣B∣=ΔA|B| = \Delta_A, the complete bipartite graph on A∪BA \cup B has ΔAΔB\Delta_A\Delta_B edges and all edges need distinct colors. Steger and Yu [19] proved Conjecture 1 for Δ(G)=3\Delta(G) = 3. Conjecture 2 is confirmed when one of ΔA,ΔB\Delta_A, \Delta_B is at most 2 (Nakprasit [17]) or at most 3 (Huang, Yu and Zhou [13]). For large degrees, Hao, Yang and Yu [12] proved χs′(G)≤1.676ΔAΔB\chi'_s(G) \le1.676\Delta_A\Delta_B when ΔAΔB\Delta_A\Delta_B is sufficiently large. Davey, Hurley, de Joannis de Verclos, Kang and Volec [6] proved χs′(G)≤1.6255Δ(G)2\chi'_s(G) \le1.6255\Delta(G)^2 for bipartite GG with Δ(G)\Delta(G) sufficiently large, χs′(G)≤1.6633ΔAΔB\chi'_s(G) \le1.6633\Delta_A\Delta_B when ΔB/ΔA\Delta_B/\Delta_A is a fixed rational number and ΔA\Delta_A is sufficiently large, and Conjecture 2 holds asymptotically almost surely for random bipartite graphs whose two parts have comparable sizes. Before [6, 12], no general improvement over the bounds for arbitrary graphs was known in the bipartite setting [6].

Let M(G)\mathcal{M}(G) be the set of induced matchings of GG. The fractional strong chromatic index of GG is

χs,f′(G)=min⁡{∑M∈M(G)wM:wM≥0 for all M, ∑M∈M(G),M∋ewM≥1 for every e∈E(G)}.\chi'_{s,f}(G) = \min\left\{ \sum_{M \in\mathcal{M}(G)} w_M : w_M \ge0 \text{ for all } M,\ \sum_{\substack{M \in\mathcal{M}(G),\\ M \ni e}} w_M \ge1 \text{ for every } e \in E(G) \right\}.

Requiring wM∈{0,1}w_M \in\{0,1\} gives χs′(G)\chi'_s(G), so χs,f′(G)\chi'_{s,f}(G) is the optimum of the linear programming relaxation of this integer program, and χs,f′(G)≤χs′(G)\chi'_{s,f}(G) \le\chi'_s(G). Equivalently, χs,f′(G)\chi'_{s,f}(G) is the fractional chromatic number of L(G)2L(G)^2, whose independent sets are exactly the induced matchings of GG; see Śleszyńska-Nowak [18]. Cames van Batenburg, Kang and Pirot [5] showed that χs,f′(G)≤1.5Δ(G)2\chi'_{s,f}(G) \le1.5\Delta(G)^2 for bipartite GG; Dębski [7] improved it to 1.4762Δ21.4762\Delta^2.

Our first result is the fractional version of Conjecture 2.

Theorem 1.1. Every bipartite graph GG with parts AA and BB satisfies χs,f′(G)≤ΔAΔB\chi'_{s,f}(G) \le\Delta_A\Delta_B.

Since an induced matching in the complete bipartite graph KΔA,ΔBK_{\Delta_A,\Delta_B} contains exactly one edge, χs,f′(KΔA,ΔB)=ΔAΔB\chi'_{s,f}(K_{\Delta_A,\Delta_B}) = \Delta_A\Delta_B and Theorem 1.1 is tight. Our second result is an asymptotic version of Conjecture 2 with an explicit error term.

Theorem 1.2. Let GG be a bipartite graph with parts AA and BB and Δ=max⁡{ΔA,ΔB}\Delta= \max\{\Delta_A, \Delta_B\}. Then

χs′(G)≤(1+o(1))ΔAΔB,\chi'_s(G) \le(1 + o(1))\Delta_A\Delta_B,

where o(1)o(1) is a quantity depending only on Δ\Delta that tends to 0 as Δ→∞\Delta\to\infty. More precisely,

χs′(G)≤(1+12(ln⁡Δ)1/2Δ1/4)ΔAΔB.\chi'_s(G) \le\left(1 + 12\frac{(\ln\Delta)^{1/2}}{\Delta^{1/4}}\right)\Delta_A\Delta_B.

The main ingredient in our proofs is a simple coloring lemma based on linear orders of one part of the bipartition. Given a linear order of AA, let each vertex b∈Bb \in B select the edge joining it to its first neighbor in that order. Lemma 2.3 shows that the selected edges can be strongly colored with at most ΔA\Delta_A colors. Choosing the order at random then yields the fractional bound in Theorem 1.1.

For the ordinary strong chromatic index, we use several linear orders of AA and their reverses. These orders produce a collection of columns to which the edges are assigned. Lemma 2.3 reduces the problem to balancing the number of edges assigned to each column around each vertex of AA. We obtain the required balance using the Lovász Local Lemma, which leads to Theorem 1.2.

The paper is organized as follows. Section 2 collects the probabilistic tools and proves the column lemma; both are key ingredients in our proof. The proof of Theorem 1.1 is presented in Section 3. Finally, in Section 4, we first construct balanced families of orders and develop the randomized rounding argument, and then use them to prove Theorem 1.2.

Preliminaries

For a vertex vv we write N(v)N(v) for its neighborhood and d(v)=∣N(v)∣d(v) = |N(v)| for its degree; ln⁡\ln is the natural logarithm and [n]={1,…,n}[n] = \{1,\ldots,n\}. Throughout, GG is a bipartite graph with parts AA and BB; we write each edge as xbxb with x∈Ax \in A and b∈Bb \in B. Vertices of degree 0 play no role, and we assume that every vertex of BB has degree at least 1.

Two distinct edges of a graph conflict if they share an endpoint or are joined by an edge. Since GG is bipartite, two distinct edges xbxb and x′b′x'b', where x,x′∈Ax,x' \in A and b,b′∈Bb,b' \in B, conflict if and only if x=x′x=x', b=b′b=b', xb′∈E(G)xb' \in E(G), or x′b∈E(G)x'b \in E(G). Hence a set of edges is an induced matching if and only if no two of its edges conflict, and a strong edge-coloring is a coloring of E(G)E(G) in which conflicting edges receive distinct colors.

We use two probabilistic tools. The first is a form of the Chernoff and Bernstein inequalities, see [15 Theorems 2.1 and 2.8].

Lemma 2.1. Let SS be a sum of finitely many independent random variables with values in {0,1}\{0,1\}, and let μ\mu be the expected value of SS. Then for every t≥0t \ge0,

Pr⁡(S≥μ+t)≤exp⁡(−t22(μ+t/3))andPr⁡(S≤μ−t)≤exp⁡(−t22μ).\Pr(S \ge\mu+t) \le\exp\left(-\frac{t^2}{2(\mu+t/3)}\right) \quad\text{and}\quad \Pr(S \le\mu-t) \le\exp\left(-\frac{t^2}{2\mu}\right).

The second is the symmetric Lovász Local Lemma, see [1 Corollary 5.1.2].

Lemma 2.2 (Lovász Local Lemma). Let O1,…,On\mathcal{O}_1,\ldots,\mathcal{O}_n be events, each having probability at most pp. Suppose that each Oi\mathcal{O}_i is mutually independent of all but at most dd of the other events. If e⋅p⋅(d+1)≤1e \cdot p \cdot(d+1) \le1, then Pr⁡(⋂i=1nOi)>0\Pr\left(\bigcap_{i=1}^{n}\mathcal{O}_i\right)>0. In particular, with positive probability none of the events O1,…,On\mathcal{O}_1,\ldots,\mathcal{O}_n occurs.

For our purposes, the underlying probability space is a product of finitely many independent random variables, and each event Oi\mathcal{O}_i is determined by a set SiS_i of these variables. In this situation Oi\mathcal{O}_i is mutually independent of the family of all events Oj\mathcal{O}_j with Sj∩Si=∅S_j \cap S_i=\varnothing, which is how the hypothesis of Lemma 2.2 will be verified.

Let K>0K>0 be an integer and let σ1,…,σK\sigma_1,\ldots,\sigma_K be linear orders of AA. For each i∈[K]i \in[K], associate two columns, denoted by (i,−)(i,-) and (i,+)(i,+), corresponding to rules to assign the first and last neighbors of b∈Bb \in B in the order σi\sigma_i, respectively. Let J={(i,−),(i,+):i∈[K]}J=\{(i,-),(i,+):i \in[K]\}, and for each b∈Bb \in B and j∈Jj \in J, the center cj(b)∈N(b)c_j(b) \in N(b) is defined by

cj(b)={min⁡σiN(b),j=(i,−),max⁡σiN(b),j=(i,+).c_j(b)= \begin{cases} \min_{\sigma_i}N(b), & j=(i,-),\\ \max_{\sigma_i}N(b), & j=(i,+). \end{cases}

For y∈N(b)y \in N(b), let My(b)={j∈J:cj(b)=y}M_y(b)=\{j \in J:c_j(b)=y\} be the set of columns in which yy is the center of bb, and let my(b)=∣My(b)∣m_y(b)=|M_y(b)|. For fixed bb, My(b)∩My′(b)=∅M_y(b)\cap M_{y'}(b)=\varnothing, where y≠y′∈N(b)y\ne y'\in N(b), and ⋃y∈N(b)My(b)=J\bigcup_{y\in N(b)}M_y(b)=J. If d(b)≥2d(b)\ge2, then my(b)m_y(b) is the number of indices ii for which yy is the σi\sigma_i-smallest or the σi\sigma_i-largest vertex of N(b)N(b); if d(b)=1d(b)=1, then my(b)=2Km_y(b)=2K.

Lemma 2.3 (Column lemma). Let GG be a bipartite graph with parts AA and BB. Let Vj⊆BV_j \subseteq B for j∈Jj \in J, and let Ej={cj(b)b:b∈Vj}E_j=\{c_j(b)b:b \in V_j\}.

  1. For every j∈Jj \in J, the edge set EjE_j can be partitioned into at most max⁡x∈A∣N(x)∩Vj∣\max_{x\in A}|N(x)\cap V_j| induced matchings of GG.

  1. If every edge of GG lies in at least one of the sets EjE_j, then

χs′(G)≤∑j∈Jmax⁡x∈A∣N(x)∩Vj∣.\chi'_s(G)\le\sum_{j\in J}\max_{x\in A}|N(x)\cap V_j|.

Proof. (a) Let j=(i,−)j=(i,-); for j=(i,+)j=(i,+) replace σi\sigma_i by its reverse in the following argument. Put λ=max⁡x∈A∣N(x)∩Vj∣\lambda=\max_{x\in A}|N(x)\cap V_j|. Every b∈Vjb\in V_j contributes exactly one edge to EjE_j, namely cj(b)bc_j(b)b. Color the edges of EjE_j one by one, processing their centers in increasing σi\sigma_i-order and the edges with a common center in any order, and give each edge a color in [λ][\lambda] that is not used on an already colored edge conflicting with it.

We show that such a color always exists. Let xb∈Ejxb \in E_j, so x=cj(b)x=c_j(b), and let x′b′∈Ejx'b' \in E_j be an already colored edge that conflicts with xbxb. Then b′≠bb' \ne b, since bb contributes only one edge to EjE_j, and x′≤σixx' \le_{\sigma_i} x, since centers are processed in increasing order. If x′≠xx' \ne x and x′b∈E(G)x'b \in E(G), then x′x' is a neighbor of bb with x′<σix=min⁡σiN(b)x' <_{\sigma_i} x = \min_{\sigma_i} N(b), which is impossible. As b≠b′b \ne b', the definition of conflict leaves two possibilities: x′=xx'=x, or xb′∈E(G)xb' \in E(G). In both cases xb′∈E(G)xb' \in E(G), and hence, b′∈N(x)b' \in N(x). Therefore, every already colored edge conflicting with xbxb is of the form cj(b′)b′c_j(b')b' with b′∈(N(x)∩Vj)∖{b}b' \in(N(x) \cap V_j) \setminus\{b\}. There are at most λ−1\lambda-1 such edges, so a color in [λ][\lambda] is available. In the resulting coloring no two conflicting edges have the same color, so every color class is an induced matching of GG.

(b) Assign each edge to one of the sets EjE_j containing it. Color the edges assigned to EjE_j as in (a), using a palette of max⁡x∣N(x)∩Vj∣\max_x |N(x) \cap V_j| colors, with pairwise disjoint palettes for different columns. Since distinct columns use disjoint palettes, any two edges receiving the same color belong to the same EjE_j, and hence do not conflict by part (a). □

Remark 2.4. The choice of the first neighbor is used exactly once in the proof: it excludes conflicts through an edge x′bx'b with x′x' preceding xx. Figure 1 shows a small example. The bound in Lemma 2.3(a) is attained, for instance, by a complete bipartite graph with a single column and Vj=BV_j=B.

Figure 1. The order σ\sigma of AA is x1<x2<x3<x4<x5x_1 < x_2 < x_3 < x_4 < x_5. Each bib_i keeps the edge to its σ\sigma-first neighbor (thick edges). Lemma 2.3(a), with one column and Vj=BV_j=B, guarantees a strong coloring of the thick edges with max⁡xd(x)=3\max_x d(x)=3 colors; here the procedure of its proof, always taking the smallest available color, uses two: solid edges x1b1,x2b2x_1b_1,x_2b_2 and dashed edges x1b4,x3b3x_1b_4,x_3b_3. Note that x3b3x_3b_3 and x1b1x_1b_1 conflict (via the edge x3b1x_3b_1), as do x3b3x_3b_3 and x2b2x_2b_2 (via x3b2x_3b_2), while x3b3x_3b_3 and x1b4x_1b_4 do not.

proof of Theorem 1.1: the fractional bound

The proof of Theorem 1.1 has two parts. First, a fractional strong edge-coloring can be obtained from a suitable probability distribution on the induced matchings of GG (Lemma 3.1). Second, a single random order of AA produces a random induced matching that contains every edge with probability at least 1/(ΔAΔB)1/(\Delta_A\Delta_B).

Lemma 3.1. Suppose there exists a probability distribution on the induced matchings of GG such that a random induced matching MM drawn from this distribution satisfies Pr⁡(e∈M)≥p\Pr(e \in M) \ge p for every edge e∈E(G)e \in E(G). Then χs,f′(G)≤1p\chi'_{s,f}(G) \le\frac{1}{p}.

Proof. For every induced matching M′M' of GG put wM′=Pr⁡(M=M′)/pw_{M'}=\Pr(M=M')/p. These weights are nonnegative, and since the probabilities Pr⁡(M=M′)\Pr(M=M') add up to 1, the weights add up to 1/p1/p. For every edge ee,

∑e∈M′wM′=1p∑e∈M′Pr⁡(M=M′)=Pr⁡(e∈M)p≥1.\sum_{e\in M'} w_{M'}=\frac{1}{p}\sum_{e\in M'}\Pr(M=M')=\frac{\Pr(e\in M)}{p}\ge1.

So the weights wM′w_{M'} are admissible in the definition of χs,f′(G)\chi'_{s,f}(G), and χs,f′(G)≤∑M′wM′=1/p\chi'_{s,f}(G)\le\sum_{M'}w_{M'}=1/p. □

Proof of Theorem 1.1. By Lemma 3.1, it suffices to construct a probability distribution on the induced matchings of GG such that a random induced matching MM drawn from this distribution satisfies

Pr⁡(e∈M)≥1ΔAΔB\Pr(e \in M) \ge\frac{1}{\Delta_A\Delta_B}

for every edge e∈E(G)e \in E(G). We construct such a distribution in four steps.

Step 1: a random order. Let σ\sigma be a linear order of AA chosen uniformly at random from all linear orders of AA.

Step 2: every vertex of BB keeps one edge. Every b∈Bb \in B keeps the edge that joins bb to its σ\sigma-first neighbor. Let

Eσ={(min⁡σN(b))b:b∈B}.E_\sigma= \{(\min_\sigma N(b))b : b \in B\}.

be the set of kept edges; it contains exactly one edge at each vertex of BB.

Step 3: splitting the kept edges. Apply Lemma 2.3(a) with K=1K = 1, σ1=σ\sigma_1 = \sigma, the column j=(1,−)j = (1,-) and Vj=BV_j = B. Then Ej=EσE_j = E_\sigma and max⁡x∈A∣N(x)∩Vj∣=max⁡x∈Ad(x)=ΔA\max_{x\in A} |N(x) \cap V_j| = \max_{x\in A} d(x) = \Delta_A. Hence EσE_\sigma can be partitioned into induced matchings Mσ,1,…,Mσ,ΔAM_{\sigma,1},\ldots,M_{\sigma,\Delta_A} of GG, some of which may be empty. We fix such a partition for every linear order σ\sigma of AA.

Step 4: choosing one part. Choose t∈[ΔA]t \in[\Delta_A] uniformly at random and independently of σ\sigma, and put M=Mσ,tM = M_{\sigma,t}. Then MM is an induced matching of GG.

Now fix an edge ybyb with y∈Ay \in A and b∈Bb \in B. The edge ybyb belongs to MM exactly when the following two events occur:

(i) yb∈Eσyb \in E_\sigma, that is, yy is the σ\sigma-first vertex of N(b)N(b);

(ii) tt is the index of the part of the partition of EσE_\sigma that contains ybyb.

The order that σ\sigma induces on N(b)N(b) is uniformly random, so each of the d(b)d(b) vertices of N(b)N(b) is the σ\sigma-first one with the same probability, and (i) has probability 1/d(b)1/d(b). If (i) occurs, then ybyb lies in exactly one of the parts Mσ,1,…,Mσ,ΔAM_{\sigma,1},\ldots,M_{\sigma,\Delta_A}, and since tt is uniform on [ΔA][\Delta_A] and independent of σ\sigma, the conditional probability of (ii) is 1/ΔA1/\Delta_A. Therefore

Pr⁡(yb∈M)=1d(b)⋅1ΔA≥1ΔAΔB,\Pr(yb \in M) = \frac{1}{d(b)} \cdot\frac{1}{\Delta_A} \ge\frac{1}{\Delta_A\Delta_B},

since d(b)≤ΔBd(b) \le\Delta_B. Lemma 3.1 with p=1/(ΔAΔB)p = 1/(\Delta_A\Delta_B) gives χs,f′(G)≤ΔAΔB\chi'_{s,f}(G) \le\Delta_A\Delta_B. □

The proof of Theorem 1.2

First, suppose that k≥2k \ge2 and Δ≥1\Delta\ge1 are integers, and GG is a bipartite graph with parts AA and BB such that d(x)≤Δd(x) \le\Delta for every x∈Ax \in A and 1≤d(b)≤k1 \le d(b) \le k for every b∈Bb \in B. A vertex y∈N(b)y \in N(b) is the center of bb in exactly my(b)m_y(b) of the 2K2K columns. On average this number is 2K/d(b)≥2K/k2K/d(b) \ge2K/k; the next lemma shows that all of them can be made close to this value simultaneously.

Lemma 4.1. Let δ∈(0,1)\delta\in(0,1) and let KK be an integer with

K≥kδ2ln⁡(3k2Δ).K \ge\frac{k}{\delta^2}\ln(3k^2\Delta).

There are linear orders σ1,…,σK\sigma_1,\ldots,\sigma_K of AA such that

my(b)≥(1−δ)2Kkm_y(b) \ge(1-\delta)\frac{2K}{k}

for every b∈Bb \in B and every y∈N(b)y \in N(b).

Proof. If d(b)=1d(b) = 1, then my(b)=2Km_y(b) = 2K. If d(b)=2d(b) = 2, then in every order one vertex of N(b)N(b) is the smallest and the other is the largest, so my(b)=K≥2K/km_y(b) = K \ge2K/k. These vertices bb satisfy the conclusion for any orders.

Choose independent random labels ℓi(x)\ell_i(x), uniform in [0,1][0,1], for i∈[K]i \in[K] and x∈Ax \in A, and let σi\sigma_i order AA by increasing ℓi\ell_i; ties occur with probability 00. Let b∈Bb \in B with d=d(b)≥3d = d(b) \ge3 and let y∈N(b)y \in N(b). For each ii, the events “yy is the σi\sigma_i-smallest vertex of N(b)N(b)” and “yy is the σi\sigma_i-largest vertex of N(b)N(b)” are disjoint with probability 1/d1/d each, and those events with different iis are independent. So my(b)m_y(b) is a sum of KK independent indicator variables with mean μ=2K/d≥2K/k\mu= 2K/d \ge2K/k. By Lemma 2.1 with t=δμt = \delta\mu,

Pr⁡(my(b)<(1−δ)2Kk)≤Pr⁡(my(b)≤(1−δ)μ)≤exp⁡(−δ2μ2)≤exp⁡(−δ2Kk).\Pr\left(m_y(b) < (1-\delta)\frac{2K}{k}\right) \le\Pr\left(m_y(b) \le(1-\delta)\mu\right) \le\exp\left(-\frac{\delta^2\mu}{2}\right) \le\exp\left(-\frac{\delta^2K}{k}\right).

Let DbD_b be the event that my(b)<(1−δ)2K/km_y(b) < (1-\delta)2K/k for some y∈N(b)y \in N(b). Then Pr⁡(Db)≤kexp⁡(−δ2K/k)=:p\Pr(D_b) \le k\exp(-\delta^2K/k) =: p. The event DbD_b is determined by the labels of the vertices in N(b)N(b), so it is mutually independent of the family of events Db′D_{b'} with N(b′)∩N(b)=∅N(b')\cap N(b) = \varnothing. The number of vertices b′≠bb' \ne b with N(b′)∩N(b)≠∅N(b')\cap N(b) \ne\varnothing is at most ∑x∈N(b)(d(x)−1)≤k(Δ−1)\sum_{x\in N(b)}(d(x)-1) \le k(\Delta-1). Since K≥(k/δ2)ln⁡(3k2Δ)K \ge(k/\delta^2)\ln(3k^2\Delta),

e⋅p⋅(k(Δ−1)+1)≤e⋅k⋅kΔ⋅exp⁡(−δ2Kk)≤e3<1.e\cdot p\cdot\bigl(k(\Delta-1)+1\bigr) \le e\cdot k\cdot k\Delta\cdot\exp\left(-\frac{\delta^2K}{k}\right) \le\frac{e}{3}<1.

By Lemma 2.2, with positive probability none of the events DbD_b occurs. □

The next result may be regarded as a version of Theorem 1.2 with free parameters.

Theorem 4.2. Let δ∈(0,1)\delta\in(0,1), let KK be an integer with K≥(k/δ2)ln⁡(3k2Δ)K \ge(k/\delta^2)\ln(3k^2\Delta), and put L=ln⁡(9KkΔ)L=\ln(9Kk\Delta). Then

χs′(G)≤kΔ1−δ+2KkΔL1−δ+2KL.\chi'_s(G) \le\frac{k\Delta}{1-\delta}+2\sqrt{\frac{Kk\Delta L}{1-\delta}}+2KL.

Proof. Fix orders σ1,…,σK\sigma_1,\ldots,\sigma_K as in Lemma 4.1. For every b∈Bb \in B and every y∈N(b)y \in N(b), my(b)≥(1−δ)2Kk>0m_y(b) \ge(1-\delta)\frac{2K}{k}>0 by Lemma 4.1. Hence My(b)≠∅M_y(b) \ne\varnothing. Choose a column jb,y∈My(b)j_{b,y}\in M_y(b) uniformly at random and all choices are independent. For j∈Jj \in J put

Vj={b∈B:jb,cj(b)=j},V_j=\{b\in B:j_{b,c_j(b)}=j\},

and let Ej={cj(b)b:b∈Vj}E_j=\{c_j(b)b:b\in V_j\} as in Lemma 2.3. Since jb,y∈My(b)j_{b,y}\in M_y(b), every edge ybyb lies in EjE_j with j=jb,yj=j_{b,y}.

Fix x∈Ax\in A and j∈Jj\in J, and let

Xx,j=∣N(x)∩Vj∣=∑b∈N(x)1[jb,cj(b)=j].X_{x,j}=|N(x)\cap V_j|=\sum_{b\in N(x)}1[j_{b,c_j(b)}=j].

The summand corresponding to bb depends only on the choice jb,cj(b)j_{b,c_j(b)}, and the choices corresponding to different vertices b∈N(x)b\in N(x) are made independently. Since j∈Mcj(b)(b)j\in M_{c_j(b)}(b), the summand of bb equals 11 with probability 1/mcj(b)(b)1/m_{c_j(b)}(b), which is at most k/(2(1−δ)K)k/(2(1-\delta)K) by Lemma 4.1 (and equals 1/(2K)1/(2K) if d(b)=1d(b)=1). As d(x)≤Δd(x)\le\Delta, the expected value μx,j\mu_{x,j} of Xx,jX_{x,j} is at most

λ:=kΔ2(1−δ)K.\lambda:=\frac{k\Delta}{2(1-\delta)K}.

If μx,j<λ\mu_{x,j}<\lambda, add to Xx,jX_{x,j} the sum of r=⌈λ−μx,j⌉r=\lceil\lambda-\mu_{x,j}\rceil indicator variables, each with mean (λ−μx,j)/r(\lambda-\mu_{x,j})/r, independent of each other and of all choices jb,yj_{b,y}. The result Xx,j′X'_{x,j} is a sum of independent indicators with Xx,j′≥Xx,jX'_{x,j}\ge X_{x,j} and expected value exactly λ\lambda; if μx,j=λ\mu_{x,j}=\lambda, put Xx,j′=Xx,jX'_{x,j}=X_{x,j}. Let t=2λL+Lt=\sqrt{2\lambda L}+L. Then

t2−2λL−23Lt=43L2λL+13L2≥0,t^2-2\lambda L-\frac{2}{3}Lt=\frac{4}{3}L\sqrt{2\lambda L}+\frac{1}{3}L^2\ge0,

that is, t2/(2(λ+t/3))≥Lt^2/(2(\lambda+t/3))\ge L. By Lemma 2.1,

Pr⁡(Xx,j≥λ+t)≤Pr⁡(Xx,j′≥λ+t)≤exp⁡(−L)=19KkΔ.\Pr(X_{x,j}\ge\lambda+t)\le\Pr(X'_{x,j}\ge\lambda+t)\le\exp(-L)=\frac{1}{9Kk\Delta}.

Let Ox,jO_{x,j} be the event Xx,j≥λ+tX_{x,j}\ge\lambda+t. It is determined by the choices jb,yj_{b,y} with b∈N(x)b\in N(x), so it is mutually independent of the family of events Ox′,j′O_{x',j'} with N(x′)∩N(x)=∅N(x')\cap N(x)=\varnothing. The number of vertices x′x' with N(x′)∩N(x)≠∅N(x') \cap N(x) \ne\emptyset, including xx itself, is at most 1+∑b∈N(x)(d(b)−1)≤1+Δ(k−1)≤kΔ1+\sum_{b\in N(x)}(d(b)-1)\le1+\Delta(k-1)\le k\Delta; hence the number of pairs (x′,j′)(x',j') with N(x′)∩N(x)≠∅N(x')\cap N(x)\ne\emptyset, including (x,j)(x,j), is at most 2KkΔ2Kk\Delta. Since

e⋅19KkΔ⋅2KkΔ=2e9<1,e\cdot\frac{1}{9Kk\Delta}\cdot2Kk\Delta=\frac{2e}{9}<1,

Lemma 2.2 shows that for some choice of the columns jb,yj_{b,y} we have Xx,j<λ+tX_{x,j}<\lambda+t for all x∈Ax\in A and j∈Jj\in J. For this choice, Lemma 2.3(b) gives

χs′(G)≤∑j∈Jmax⁡x∈AXx,j≤2K(λ+t)=kΔ1−δ+2K2λL+2KL.\chi'_s(G)\le\sum_{j\in J}\max_{x\in A}X_{x,j}\le2K(\lambda+t)=\frac{k\Delta}{1-\delta}+2K\sqrt{2\lambda L}+2KL.

and 2K2λL=2KkΔL/(1−δ)2K\sqrt{2\lambda L}=2\sqrt{Kk\Delta L/(1-\delta)}.

Now we are ready to prove Theorem 1.2.

Proof of Theorem 1.2. Let

u=(ln⁡Δ)1/2Δ1/4,so thatu2=ln⁡ΔΔ1/2.u=\frac{(\ln\Delta)^{1/2}}{\Delta^{1/4}}, \qquad\text{so that}\qquad u^2=\frac{\ln\Delta}{\Delta^{1/2}}.

Choose Δ\Delta large enough so that u<1/10u<1/10. Put

δ=u,K=⌈ku2ln⁡(3k2Δ)⌉,L=ln⁡(9KkΔ).\delta=u,\qquad K=\left\lceil\frac{k}{u^2}\ln(3k^2\Delta)\right\rceil,\qquad L=\ln(9Kk\Delta).

Then δ∈(0,1)\delta\in(0,1) and KK satisfies the hypothesis of Theorem 4.2. Dividing the bound of Theorem 4.2 by kΔ=ΔAΔBk\Delta=\Delta_A\Delta_B gives

χs′(G)ΔAΔB≤11−u+211−u⋅KLkΔ+2KLkΔ.(1)\frac{\chi'_s(G)}{\Delta_A\Delta_B}\le\frac{1}{1-u}+2\sqrt{\frac{1}{1-u}\cdot\frac{KL}{k\Delta}}+2\frac{KL}{k\Delta}. \tag*{(1)}

We estimate KK and LL. Since k≤Δk\le\Delta, we have ln⁡(3k2Δ)≤ln⁡3+3ln⁡Δ≤4ln⁡Δ\ln(3k^2\Delta)\le\ln3+3\ln\Delta\le4\ln\Delta. So

K=⌈ku2ln⁡(3k2Δ)⌉≤⌈4kln⁡Δu2⌉=⌈4kΔ1/2⌉≤4kΔ1/2+1.K=\left\lceil\frac{k}{u^2}\ln(3k^2\Delta)\right\rceil\le\left\lceil\frac{4k\ln\Delta}{u^2}\right\rceil=\left\lceil4k\Delta^{1/2}\right\rceil\le4k\Delta^{1/2}+1.

Hence L=ln⁡(9KkΔ)≤ln⁡(9⋅4.001⋅Δ7/2)≤ln⁡37+7/2ln⁡ΔL=\ln(9Kk\Delta)\le\ln(9\cdot4.001\cdot\Delta^{7/2})\le\ln37+7/2\ln\Delta. Therefore,

KLkΔ≤(4kΔ1/2+1)⋅(ln⁡37+7/2ln⁡Δ)kΔ≤4⋅3.6ln⁡ΔΔ1/2=14.4u2≤1.44u.\frac{KL}{k\Delta}\le\frac{(4k\Delta^{1/2}+1)\cdot(\ln37+7/2\ln\Delta)}{k\Delta}\le4\cdot3.6\frac{\ln\Delta}{\Delta^{1/2}}=14.4u^2\le1.44u.

Finally, u≤1/10u\le1/10 gives 11−u=1+u1−u≤1+109u\frac{1}{1-u}=1+\frac{u}{1-u}\le1+\frac{10}{9}u and 11−u≤109\frac{1}{1-u}\le\frac{10}{9}. So the three terms on the right-hand side of (1) satisfy

11−u≤1+109u,211−u⋅KLkΔ≤2109⋅14.4u2=8u,2KLkΔ≤2.88u.\frac{1}{1-u}\le1+\frac{10}{9}u,\qquad 2\sqrt{\frac{1}{1-u}\cdot\frac{KL}{k\Delta}}\le2\sqrt{\frac{10}{9}\cdot14.4u^2}=8u,\qquad 2\frac{KL}{k\Delta}\le2.88u.

Adding them,

χs′(G)ΔAΔB≤1+(109+8+2.88)u<1+12u.\frac{\chi'_s(G)}{\Delta_A\Delta_B}\le1+\left(\frac{10}{9}+8+2.88\right)u<1+12u.

Remark 4.3. The choice of the side AA in the proof matters: the parameters L0L_0 and LL grow with ln⁡k\ln k, and the error term is small because k≤Δk\le\Delta. The proof also shows where the error term comes from. The factor 1/(1−δ)1/(1-\delta) is the price for the imbalance of the counts my(b)m_y(b) among KK random orders, which forces KK to be of order klog⁡Δ/δ2k\log\Delta/\delta^2; the term 2KkΔL/(1−δ)2\sqrt{Kk\Delta L/(1-\delta)} is the price for the fluctuations of the loads Xx,jX_{x,j}, whose expected values λ\lambda are of order kΔ/Kk\Delta/K. Balancing the two gives the relative error of order (log⁡Δ)1/2Δ−1/4(\log\Delta)^{1/2}\Delta^{-1/4}. We could improve 12 in Theorem 1.2 to a smaller constant if we are more careful in calculation.

AI usage declaration

Claude Opus 5.5 was used to assist in developing the proofs and in preparing the text of this article. The main ideas are due to the authors, who have verified all mathematical content and take full responsibility for its correctness.

References

References

  1. [1]N. Alon and J. H. Spencer, The Probabilistic Method, 4th ed., Wiley, Hoboken, NJ, 2016.
  2. [2]M. Bonamy, T. Perrett and L. Postle, Colouring graphs with sparse neighbourhoods: bounds and applications, J. Combin. Theory Ser. B 155 (2022), 278–317.arxiv.org/abs/1810.06704
  3. [3]R. A. Brualdi and J. J. Quinn Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993), 51–58.DOI
  4. [4]H. Bruhn and F. Joos, A stronger bound for the strong chromatic index, Combin. Probab. Comput. 27 (2018), 21–43.
  5. [5]W. Cames van Batenburg, R. J. Kang and F. Pirot, Strong cliques and forbidden cycles, Indag. Math. 31 (2020), 64–82.
  6. [6]E. Davey, E. Hurley, R. de Joannis de Verclos, R. J. Kang and J. Volec, Strong edge-colouring via local flag algebras, arXiv:2607.17421, 2026.arxiv.org/abs/2607.17421
  7. [7]M. Dębski, Fractional strong chromatic index of bipartite graphs, Discrete Math. (2017), doi:10.1016/j.disc.2017.02.006.DOI
  8. [8]P. Erdős and J. Nešetřil, Problem, in: G. Halász and V. T. Sós (eds.), Irregularities of Partitions, Springer, Berlin, 1989, 162–163.
  9. [9]R. J. Faudree, A. Gyárfás, R. H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990), 205–211.
  10. [11]J.-L. Fouquet and J.-L. Jolivet, Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin. 16A (1983), 141–150.
  11. [12]Y. Hao, T. Yang and X. Yu, Strong chromatic index of bipartite graphs, arXiv:2606.23824, 2026.arxiv.org/abs/2606.23824
  12. [13]M. Huang, G. Yu and X. Zhou, The strong chromatic index of (3, Δ)-bipartite graphs, Discrete Math. 340 (2017), 1143–1149.
  13. [14]E. Hurley, R. de Joannis de Verclos and R. J. Kang, An improved procedure for colouring graphs of bounded local density, Adv. Comb. (2022), Paper No. 7.
  14. [15]S. Janson, T. Łuczak and A. Ruciński, Random Graphs, Wiley, New York, 2000.
  15. [16]M. Molloy and B. Reed, A bound on the strong chromatic index of a graph, J. Combin. Theory Ser. B 69 (1997), 103–109.DOI
  16. [17]K. Nakprasit, A note on the strong chromatic index of bipartite graphs, Discrete Math. 308 (2008), 3726–3728.DOI
  17. [18]M. Śleszyńska-Nowak, Clique number of the square of a line graph, Discrete Math. 339 (2016), 1551–1556.
  18. [19]A. Steger and M.-L. Yu, On induced matchings, Discrete Math. 120 (1993), 291–295.DOI

Paper details

vlnc:W_caewsjtm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Opus 5.5

View statement
Looking for related papers…
Contents