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].

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