A note on the strong edge-coloring of outerplanar graphs with maximum degree 3
Tóm tắt
A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, are assigned different colors. The strong chromatic index of G is the smallest integer k for which G has a strong k-edge-coloring. In this paper, we have shown that the strong chromatic index is no larger than 6 for outerplanar graphs with maximum degree 3.
Tài liệu tham khảo
Andersen, L.D. The strong chromatic index of a cubic graph is at most 10. Discrete Math., 108: 231–252 (1992)
Cranston, D.W. Strong edge-coloring of graphs with maximum degree 4 using 22 colors. Discrete Math., 306: 2772–2778 (2006)
Erdös, P. Problems and results in combinatorial analysis and graph theory. Discrete Math., 72: 81–92 (1988)
Erdös, P., Nešetřil, J. Problem. In: Irregularities of Partions, ed. by G. Halász, V.T. Sös, Springer, Berlin, 1989, 162–163
Faudree, R.J., Schelp, R.H., Gyárfás, A., Tuza, Zs. The strong chromatic index of graphs. Ars Combin., 29B: 205–211 (1990)
Horák, P., Qing, H., Trotter, W.T. Induced matchings in cubic graphs. J. Graph Theory, 17: 151–160 (1993)
Lai, H.H., Lih, K.W., Tsai, P.Y. The strong chromatic index of Halin graphs. Discrete Math., 312: 1536–1541 (2012)
Liu, S., Chen, X., Chen, H. The strong edge-coloring of Halin graphs with Δ ≥ 4. Acta Math. Appl. Sin., 31:1–7 (2008) (in Chinese)
Mahdian, M. The strong chromatic index of graphs. M.Sc. Thesis, Department of Computer Science, University of Toronto, 2000
Molloy, M., Reed, B. A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B, 69: 103–109 (1997)
Quinn, J.J., Benjamin, A.T. Strong chromatic index of subset graphs. J. Graph Theory, 24: 267–273 (1997)
Shiu, W.C., Lam, P.C.B., Tam, W.K. On strong chromatic index of Halin graph. J. Combin. Math. Combin. Comput., 57: 211–222 (2006)
Togni, O. Strong chromatic index of products of graphs. Discrete Math. Theor. Comput. Sci., 9: 47–56 (2007)
West, D.B. Introduction to Graph Theory, 2nd ed. Prentice Hall, 2001
West, D.B. Strong edge-coloring, Open problems-Graph theory and Combinatorics, http://www.math.uiuc.edu/west/openp/strongedge.html, 2003