Strong edge-coloring of graphs with maximum degree 4 using 22 colors. (English) Zbl 1143.05025
Erdős and Nesetril conjectured that every graph of even maximal degree \(\Delta\) can be strongly edge-colored by \(\frac54\Delta^2\) colors and if \(\Delta\) is odd by \(\frac14(5\Delta^2-2\Delta+1)\) colors. In this note the author gives a constructive contribution to the special case \(\Delta=4\).
Reviewer: Bert Randerath (Köln)
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
References:
| [1] | Andersen, L. D., The strong chromatic index of a cubic graph is at most 10, Topological, algebraical and combinatorial structures, Frolík’s memorial volume, Discrete Math., 108, 1-3, 231-252 (1992) · Zbl 0756.05050 |
| [2] | Chung, F. R.K.; Gyárfás, A.; Tuza, Zs.; Trotter, W. T., The maximum number of edges in \(2 K_2\)-free graphs of bounded degree, Discrete Math., 81, 2, 129-135 (1990) · Zbl 0698.05039 |
| [3] | Faudree, R. J.; Gyárfás, A.; Schelp, R. H.; Tuza, Zs., The strong chromatic index of graphs, Ars Combin., 29B, 205-211 (1990) · Zbl 0721.05018 |
| [4] | P. Horák, The strong chromatic index of graphs with maximum degree four, Contemporary Methods in Graph Theory, 1990, pp. 399-403.; P. Horák, The strong chromatic index of graphs with maximum degree four, Contemporary Methods in Graph Theory, 1990, pp. 399-403. · Zbl 0715.05023 |
| [5] | West, D. B., Introduction to Graph Theory (2001), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [6] | D.B. West, Strong edge-coloring, Open Problems—Graph Theory and Combinatorics, \( \langle;\) http://www.math.uiuc.edu/\( \sim;\rangle;\); D.B. West, Strong edge-coloring, Open Problems—Graph Theory and Combinatorics, \( \langle;\) http://www.math.uiuc.edu/\( \sim;\rangle;\) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
