Strong Edge-Coloring (1985 and 1989)

Originator(s): P. Erdös and J. Ne\v{s}et\v{r}il (Conjecture 1, 1985). R. Faudree, A. Gyárfás, R. Schelp, and Zs. Tuza [FGST] (Conjecture 2, 1989).

Definition: A strong edge-coloring of a graph G is a edge-coloring in which every color class is an induced matching; that is, any two vertices belonging to distinct edges with the same color are not adjacent. The strong chromatic index s'(G) is the minimum number of colors in a strong edge-coloring of G.

Conjectures: If G is a simple graph with maximum degree D, then
1) s'(G) <= 5D2/4 if D is even, and s'(G) <= (5D2-2D+1)/4 if D is odd.
2) s'(G) <= D2 if G is bipartite. (Stronger versions described below.)
3) s'(G) <= 7 if G is bipartite with maximum degree 3 and has no 4-cycle.
4) s'(G) <= 9 if G is planar and 3-regular.
5) s'(G) <= 6 if G is bipartite and the sum the the degrees of any two adjacent vertices is at most 5.

Background/motivation: Finding the best possible bound on s'(G) in terms of D would be an analogue of Vizing's Theorem for strong edge-coloring. One could also consider the problem for multigraphs, as with edge-coloring, but the conjectures above are stated for simple graphs.

The conjectured bounds would be sharp. In a 2K2-free graph, every color class has size 1. Expanding each vertex of a 5-cycle into an independent set of size D/2 yields such a graph with 5D2/4 edges when D is even, and a similar construction achieves the bound when D is odd. Chung, Gyárfás, Trotter, and Tuza [CGTT] proved that this is the maximum number of edges in a 2K2-free graph with maximum degree D.

When G is bipartite, KD,D shows that Conjecture 2 is sharp. For Conjecture 4, an extremal example is the prism over a triangle; that is, the cartesian product of C3 and K2.

Comments/Partial results: Greedy coloring (coloring the edges in some order, using on each edge when encountered the least-indexed color available for it at that time) yields s'(G) <= 2D(D-1)+1. Erdös and Ne\v{s}et\v{r}il asked whether the leading coefficient could be improved. Using probabilistic methods, Molloy and Reed [MR] proved that there is a positive constant c such that, for sufficiently large D, every graph with maximum degree D has strong chromatic index at most (2-c)D2.

The greedy bound proves Conjecture 1 for D <= 2. For D=3, the conjectured bound of 10 was proved independently by Horák, He, and Trotter [HHT] and by Andersen [A]. For D=4, the conjectured bound is 20, and Horák [H] proved that 23 colors suffice.

Steger and Yu [SY] proved Conjecture 2 for D=3. A stronger version of Conjecture 2, due to Brualdi and Quinn [BQ], states that s'(G) is bounded by D1D2, where D1 and D2 are the maximum degrees among vertices in the two partite sets, respectively. Quinn and Benjamin [QB] proved this for a special class of bipartite graphs whose partite sets are the k-sets and l-sets in [m], adjacent when the two sets share exactly j elements. Quinn and Sundberg [QS] proved it for the incidence bigraph of the k-sets in [m].

Mahdian [M] proved that if G is C4-free, then s'(G) <= (2+o(1))D2/lnD, and this is asymptotically best possible. He also conjectured that s'(G) <= D2 when G is C5-free, which would strengthen Conjecture 2. Skupie\'n [S] posed more general conjectures when the distance between edges with the same color must be at least d, and he determined the values of these parameters on hypercubes. A paper by Chen and Chen [CC] suggests a new upper bound in its title, but MathReviews has no review of it to state what the result may be.

Cranston [C] proved that if G has maximum degree 4, then G has a strong edge-coloring with at most 22 colors. Wu and Lin [WL] proved Conjecture 5 in a stronger form, replacing the requirement of being bipartite with forbidding of a single graph H0.

References:
[A] Andersen, L. D. The strong chromatic index of a cubic graph is at most 10. Topological, algebraical and combinatorial structures. Frolík's memorial volume. Discrete Math. 108 (1992), no. 1-3, 231--252.
[BQ] Brualdi, R. A.; Quinn Massey, J. J. Quinn Incidence and strong edge colorings of graphs. Discrete Math. 122 (1993), no. 1-3, 51--58.
[CC] Chen, X. G.; Chen, D. L. A new upper bound of the strong chromatic index. Appl. Math. J. Chinese Univ. Ser. A 17 (2002), no. 3, 264--268.
[C] Cranston, D. W. Strong edge-coloring of graphs with maximum degree 4 using 22 colors. Discrete Math. Vol. 306 (2006), no. 21, 2772--2778.
[FGST] Faudree, R. J.; Gyárfás, A.; Schelp, R. H.; Tuza, Zs. Induced matchings in bipartite graphs. Discrete Math. 78 (1989), no. 1-2, 83--87.
[H] Horák, P. The strong chromatic index of graphs with maximum degree four. Contemporary methods in graph theory, 399--403, Bibliographisches Inst., Mannheim, 1990.
[HHT] Horák, P.; He, Q.; Trotter, W. T. Induced matchings in cubic graphs. J. Graph Theory 17 (1993), no. 2, 151--160.
[M] Mahdian, M. The strong chromatic index of C4-free graphs. Proceedings of the Ninth International Conference "Random Structures and Algorithms" (Poznan, 1999). Random Structures Algorithms 17 (2000), no. 3-4, 357--375.
[MR] Molloy, M.; Reed, B. A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B 69 (1997), no. 2, 103--109.
[QB] Quinn, J. J.; Benjamin, A. T. Strong chromatic index of subset graphs. J. Graph Theory 24 (1997), no. 3, 267--273.
[QS] Quinn, J. J.; Sundberg, E. L. Strong chromatic index in subset graphs. Ars Combin. 49 (1998), 155--159.
[S] Skupie\'n, Z. Some maximum multigraphs and edge/vertex distance colourings. Discuss. Math. Graph Theory 15 (1995), no. 1, 89--106.
[SY] Steger, A.; Yu, M.-L. On induced matchings. Discrete Math. 120 (1993), no. 1-3, 291--295.
[WL] Wu, Jianzhuan and Lin, Wensong. The strong chromatic index of a class of graphs. Discrete Math. 308 (2008), no. 24, 6254--6261.