![](/files/happy5.png)
Strong edge colouring conjecture
A strong edge-colouring of a graph is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index
is the minimum number of colours in a strong edge-colouring of
.
![$$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$](/files/tex/a63811dfccf4e3128accc3daca7041ff5097e2a2.png)
![$$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$](/files/tex/987d7e1dcf43bb92750a5d1dffe79abc224035c2.png)
The conjectured bounds would be sharp. When is even, expanding each vertex of a
-cycle into a stable set of size
yields such a graph with
edges in which the largest induced matching has size
. A similar construction achieves the bound when
is odd.
Greedy colouring the edges yields . Using probabilistic methods, Molloy and Reed~[MoRe97] proved that there is a positive constant
such that, for sufficiently large
, every graph with maximum degree
has strong chromatic index at most
.
The greedy bound proves the conjecture for . For
, the conjectured bound of 10 was proved independently by Hor\'ak, He, and Trotter[HHT] and by Andersen [A]. For
, the conjectured bound is 20, and Cranston [C] proved that 22 colours suffice.
For a bipartite graph , Faudree et al. [FGST] conjectured that
. This is implied by the stronger conjecture due to Kaiser.
![$ G=((A_1,A_2),E) $](/files/tex/c79dbe018db5505711d3e6f03b190cf166091f20.png)
![$ A_1 $](/files/tex/cad9bfcb5f598c9f3e6780be0cf006515579b1fb.png)
![$ \Delta_1 $](/files/tex/99c7c76b15504ec54cca04dc276b441e9e0ed12b.png)
![$ A_2 $](/files/tex/0bb10db7db133ab8a6230eb43de74ced787a1bba.png)
![$ \Delta_2 $](/files/tex/0185a80a5ca1cf796ead5cc912e586e12e6cb896.png)
![$ s\chi'(G)\leq \Delta_1\Delta_2 $](/files/tex/9c75ab10a570936d6dceb970c32d75b0824cac35.png)
Bibliography
[A] L. D. Andersen. The strong chromatic index of a cubic graph is at most 10. Discrete Math., 108(1-3):231--252, 1992.
[C] D. W. Cranston. Strong edge-coloring of graphs with maximum degree 4 using 22 colors. Discrete Math., 306(21):2772--2778, 2006.
[FGST] R. J. Faudree, A. Gyárfás, R. H. Schelp, and Zs. Tuza. Induced matchings in bipartite graphs. Discrete Math., 78(1-2):83--87, 1989.
[HHT] P. Horák, Q. He, and W. T. Trotter. Induced matchings in cubic graphs. J. Graph Theory, 17(2):151--160, 1993.
* indicates original appearance(s) of problem.