# Bounding the strong chromatic index

The strong chromatic index $$\chi^*(G)$$ of a graph $$G$$ is the least number $$r$$ so that the edges of $$G$$ can be colored in $$r$$ colors in such a way that any two adjacent vertices in $$G$$ are not incident to other edges of the same color.

# Conjecture (proposed by Erdös and Nešetril [3])

Suppose $$G$$ has maximum degree $$k$$. Is it true that $$\chi^*(G)\leq \frac{5 k^2}{4}$$ if $$k$$ is even and $$\chi^*(G) \leq \frac{5k^2}{4} -\frac{k}{2}+\frac{1}{4}$$ if $$k$$ is odd?

This conjecture is open for $$k \geq 4$$, while the cases of $$k \leq 3$$ were solved by Andersen [1] and Horák, Qing and Trotter [4]. Chung, Gyárfás, Trotter and Tuza [2] proved that if $$G$$ contains no induced $$2 K_2$$, then $$G$$ has at most $$5k^2/4$$ edges. Molloy and Reed [6] proved that there exist a small but positive $$\epsilon$$ so that

$$\displaystyle \chi^*(G) \leq (2-\epsilon) k^2$$

for any $$k$$-regular graph $$G$$.

Some progress has been made for specific graphs. If $$G = G(n,p)$$ is a Erdös-Réyni random graph with $$\frac{(\log n)^{1+\epsilon}}{n} < p < n^{-\epsilon}$$ for $$0< \epsilon < 1$$, then Vu [7] showed that $$\chi^*(G) = O_k (\frac{k^2}{\log k})$$. In the case of $$C_4$$-free graphs, Mahdian proved $$\chi^*(G) \le (2+o(1))\frac{k^2}{\log k}$$ [5].

Bibliography
1 L. D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math. 108 (1992), 231-252.

2 F. R. K. Chung, A. Gyárfás, W. T. Trotter and Zs. Tuza, The maximum number of edges in $$2 K_2$$-free graphs of bounded degree, Discrete Math. 81 (1990), 129-135.

3 P. Erdös, Problems and results on chromatic numbers in finite and infinite graphs, Graph theory with applications to algorithms and computer science (Kalamazoo, MI, 1984), Wiley-Intersci. Publ., 201-213, Wiley, New York, 1985.

4 P. Horák, Qing He and W. T. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993), 151-160.

5 M. Mahdian, The strong chromatic index of $$C_4$$-free graphs, Random Structures & Algorithms - Special issue on proceedings of the ninth international conference on Random Structures and Algorithms 17 2000.

6 M. Molloy and B. Reed, A bound on the strong chromatic index of a graph, J. Comb. Theory B 69 (1997), 103-109.

7 V. H. Vu, On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs, J. Graph Theory 31 (1999), 201-226