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ö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
|