Bounding the strong chromatic index
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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ösRé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), 231252.

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), 129135.

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), WileyIntersci.
Publ., 201213, Wiley, New York, 1985.

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

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), 103109.

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), 201226
