**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) <= 5D ^{2}/4* if

2)

3)

4)

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 *2K _{2}*-free graph,
every color class has size 1. Expanding each vertex of a 5-cycle into an
independent set of size

When *G* is bipartite, *K _{D,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

**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)D ^{2}*.

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 *D _{1}D_{2}*, where

Mahdian [M] proved that if *G* is *C _{4}*-free,
then

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 *C _{4}*-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.