In this paper
AbstractIntroductionPreliminariesproof of Theorem 1.1: the fractional boundThe proof of Theorem 1.2AI usage declarationReferencesWorksMathematics
The Brualdi–Quinn conjecture on strong edge-coloring holds fractionally and asymptotically
Abstract
Let be a bipartite graph with parts and , and let and be the maximum degrees of the vertices in and in , respectively. Brualdi and Quinn conjectured that the strong chromatic index of is at most . We prove that the fractional strong chromatic index of is at most , and that the conjecture holds asymptotically: as . The error term is with . 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 is an assignment of colors to the edges of 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 is the minimum number of colors in a strong edge-coloring of . The notion was introduced by Fouquet and Jolivet [11]. For a graph of maximum degree , a greedy argument gives . Erdős and Nešetřil [8] conjectured that
Molloy and Reed [16] established the first asymptotic improvement over the greedy bound on where they proved that for sufficiently large . This was successively improved to by Bruhn and Joos [4], to by Bonamy, Perrett and Postle [2], and to by Hurley, de Joannis de Verclos and Kang [14]. More recently, Davey, Hurley, de Joannis de Verclos, Kang and Volec [6] obtained the bound 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 with maximum degree satisfies .
Brualdi and Quinn [3] proposed a stronger, asymmetric version. Let be bipartite with parts and , and let
Conjecture 2 (Brualdi and Quinn [3]). Every bipartite graph satisfies .
Both conjectures are tight: if and , the complete bipartite graph on has edges and all edges need distinct colors. Steger and Yu [19] proved Conjecture 1 for . Conjecture 2 is confirmed when one of is at most 2 (Nakprasit [17]) or at most 3 (Huang, Yu and Zhou [13]). For large degrees, Hao, Yang and Yu [12] proved when is sufficiently large. Davey, Hurley, de Joannis de Verclos, Kang and Volec [6] proved for bipartite with sufficiently large, when is a fixed rational number and 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 be the set of induced matchings of . The fractional strong chromatic index of is
Requiring gives , so is the optimum of the linear programming relaxation of this integer program, and . Equivalently, is the fractional chromatic number of , whose independent sets are exactly the induced matchings of ; see Śleszyńska-Nowak [18]. Cames van Batenburg, Kang and Pirot [5] showed that for bipartite ; Dębski [7] improved it to .
Our first result is the fractional version of Conjecture 2.
Theorem 1.1. Every bipartite graph with parts and satisfies .
Since an induced matching in the complete bipartite graph contains exactly one edge, 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 be a bipartite graph with parts and and . Then
where is a quantity depending only on that tends to 0 as . More precisely,
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 , let each vertex 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 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 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 . 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 we write for its neighborhood and for its degree; is the natural logarithm and . Throughout, is a bipartite graph with parts and ; we write each edge as with and . Vertices of degree 0 play no role, and we assume that every vertex of has degree at least 1.
Two distinct edges of a graph conflict if they share an endpoint or are joined by an edge. Since is bipartite, two distinct edges and , where and , conflict if and only if , , , or . 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 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 be a sum of finitely many independent random variables with values in , and let be the expected value of . Then for every ,
The second is the symmetric Lovász Local Lemma, see [1 Corollary 5.1.2].
Lemma 2.2 (Lovász Local Lemma). Let be events, each having probability at most . Suppose that each is mutually independent of all but at most of the other events. If , then . In particular, with positive probability none of the events occurs.
For our purposes, the underlying probability space is a product of finitely many independent random variables, and each event is determined by a set of these variables. In this situation is mutually independent of the family of all events with , which is how the hypothesis of Lemma 2.2 will be verified.
Let be an integer and let be linear orders of . For each , associate two columns, denoted by and , corresponding to rules to assign the first and last neighbors of in the order , respectively. Let , and for each and , the center is defined by
For , let be the set of columns in which is the center of , and let . For fixed , , where , and . If , then is the number of indices for which is the -smallest or the -largest vertex of ; if , then .
Lemma 2.3 (Column lemma). Let be a bipartite graph with parts and . Let for , and let .
For every , the edge set can be partitioned into at most induced matchings of .
If every edge of lies in at least one of the sets , then
Proof. (a) Let ; for replace by its reverse in the following argument. Put . Every contributes exactly one edge to , namely . Color the edges of one by one, processing their centers in increasing -order and the edges with a common center in any order, and give each edge a color in that is not used on an already colored edge conflicting with it.
We show that such a color always exists. Let , so , and let be an already colored edge that conflicts with . Then , since contributes only one edge to , and , since centers are processed in increasing order. If and , then is a neighbor of with , which is impossible. As , the definition of conflict leaves two possibilities: , or . In both cases , and hence, . Therefore, every already colored edge conflicting with is of the form with . There are at most such edges, so a color in is available. In the resulting coloring no two conflicting edges have the same color, so every color class is an induced matching of .
(b) Assign each edge to one of the sets containing it. Color the edges assigned to as in (a), using a palette of 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 , 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 with preceding . 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 .
Figure 1. The order of is . Each keeps the edge to its -first neighbor (thick edges). Lemma 2.3(a), with one column and , guarantees a strong coloring of the thick edges with colors; here the procedure of its proof, always taking the smallest available color, uses two: solid edges and dashed edges . Note that and conflict (via the edge ), as do and (via ), while and 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 (Lemma 3.1). Second, a single random order of produces a random induced matching that contains every edge with probability at least .
Lemma 3.1. Suppose there exists a probability distribution on the induced matchings of such that a random induced matching drawn from this distribution satisfies for every edge . Then .
Proof. For every induced matching of put . These weights are nonnegative, and since the probabilities add up to 1, the weights add up to . For every edge ,
So the weights are admissible in the definition of , and . □
Proof of Theorem 1.1. By Lemma 3.1, it suffices to construct a probability distribution on the induced matchings of such that a random induced matching drawn from this distribution satisfies
for every edge . We construct such a distribution in four steps.
Step 1: a random order. Let be a linear order of chosen uniformly at random from all linear orders of .
Step 2: every vertex of keeps one edge. Every keeps the edge that joins to its -first neighbor. Let
be the set of kept edges; it contains exactly one edge at each vertex of .
Step 3: splitting the kept edges. Apply Lemma 2.3(a) with , , the column and . Then and . Hence can be partitioned into induced matchings of , some of which may be empty. We fix such a partition for every linear order of .
Step 4: choosing one part. Choose uniformly at random and independently of , and put . Then is an induced matching of .
Now fix an edge with and . The edge belongs to exactly when the following two events occur:
(i) , that is, is the -first vertex of ;
(ii) is the index of the part of the partition of that contains .
The order that induces on is uniformly random, so each of the vertices of is the -first one with the same probability, and (i) has probability . If (i) occurs, then lies in exactly one of the parts , and since is uniform on and independent of , the conditional probability of (ii) is . Therefore
since . Lemma 3.1 with gives . □
The proof of Theorem 1.2
First, suppose that and are integers, and is a bipartite graph with parts and such that for every and for every . A vertex is the center of in exactly of the columns. On average this number is ; the next lemma shows that all of them can be made close to this value simultaneously.
Lemma 4.1. Let and let be an integer with
There are linear orders of such that
for every and every .
Proof. If , then . If , then in every order one vertex of is the smallest and the other is the largest, so . These vertices satisfy the conclusion for any orders.
Choose independent random labels , uniform in , for and , and let order by increasing ; ties occur with probability . Let with and let . For each , the events “ is the -smallest vertex of ” and “ is the -largest vertex of ” are disjoint with probability each, and those events with different s are independent. So is a sum of independent indicator variables with mean . By Lemma 2.1 with ,
Let be the event that for some . Then . The event is determined by the labels of the vertices in , so it is mutually independent of the family of events with . The number of vertices with is at most . Since ,
By Lemma 2.2, with positive probability none of the events occurs. □
The next result may be regarded as a version of Theorem 1.2 with free parameters.
Theorem 4.2. Let , let be an integer with , and put . Then
Proof. Fix orders as in Lemma 4.1. For every and every , by Lemma 4.1. Hence . Choose a column uniformly at random and all choices are independent. For put
and let as in Lemma 2.3. Since , every edge lies in with .
Fix and , and let
The summand corresponding to depends only on the choice , and the choices corresponding to different vertices are made independently. Since , the summand of equals with probability , which is at most by Lemma 4.1 (and equals if ). As , the expected value of is at most
If , add to the sum of indicator variables, each with mean , independent of each other and of all choices . The result is a sum of independent indicators with and expected value exactly ; if , put . Let . Then
that is, . By Lemma 2.1,
Let be the event . It is determined by the choices with , so it is mutually independent of the family of events with . The number of vertices with , including itself, is at most ; hence the number of pairs with , including , is at most . Since
Lemma 2.2 shows that for some choice of the columns we have for all and . For this choice, Lemma 2.3(b) gives
and .
Now we are ready to prove Theorem 1.2.
Proof of Theorem 1.2. Let
Choose large enough so that . Put
Then and satisfies the hypothesis of Theorem 4.2. Dividing the bound of Theorem 4.2 by gives
We estimate and . Since , we have . So
Hence . Therefore,
Finally, gives and . So the three terms on the right-hand side of (1) satisfy
Adding them,
Remark 4.3. The choice of the side in the proof matters: the parameters and grow with , and the error term is small because . The proof also shows where the error term comes from. The factor is the price for the imbalance of the counts among random orders, which forces to be of order ; the term is the price for the fluctuations of the loads , whose expected values are of order . Balancing the two gives the relative error of order . 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]N. Alon and J. H. Spencer, The Probabilistic Method, 4th ed., Wiley, Hoboken, NJ, 2016.
- [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]R. A. Brualdi and J. J. Quinn Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993), 51–58.DOI
- [4]H. Bruhn and F. Joos, A stronger bound for the strong chromatic index, Combin. Probab. Comput. 27 (2018), 21–43.
- [5]W. Cames van Batenburg, R. J. Kang and F. Pirot, Strong cliques and forbidden cycles, Indag. Math. 31 (2020), 64–82.
- [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]M. Dębski, Fractional strong chromatic index of bipartite graphs, Discrete Math. (2017), doi:10.1016/j.disc.2017.02.006.DOI
- [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]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.
- [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.
- [12]Y. Hao, T. Yang and X. Yu, Strong chromatic index of bipartite graphs, arXiv:2606.23824, 2026.arxiv.org/abs/2606.23824
- [13]M. Huang, G. Yu and X. Zhou, The strong chromatic index of (3, Δ)-bipartite graphs, Discrete Math. 340 (2017), 1143–1149.
- [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.
- [15]S. Janson, T. Łuczak and A. Ruciński, Random Graphs, Wiley, New York, 2000.
- [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
- [17]K. Nakprasit, A note on the strong chromatic index of bipartite graphs, Discrete Math. 308 (2008), 3726–3728.DOI
- [18]M. Śleszyńska-Nowak, Clique number of the square of a line graph, Discrete Math. 339 (2016), 1551–1556.
- [19]A. Steger and M.-L. Yu, On induced matchings, Discrete Math. 120 (1993), 291–295.DOI
