Geodesic
Upper Bounds for the Strong Chromatic Index of Halin Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 5-26.

Voir la notice de l'article provenant de la source Library of Science

The strong chromatic index of a graph G, denoted by χ_s^′ (G), is the minimum number of vertex induced matchings needed to partition the edge set of G. Let T be a tree without vertices of degree 2 and have at least one vertex of degree greater than 2. We construct a Halin graph G by drawing T on the plane and then drawing a cycle C connecting all its leaves in such a way that C forms the boundary of the unbounded face. We call T the characteristic tree of G. Let G denote a Halin graph with maximum degree Δ and characteristic tree T. We prove that χ_s^′ (G) ≤ 2 Δ + 1 when Δ≥ 4. In addition, we show that if Δ = 4 and G is not a wheel, then χ_s^′ (G) ≤χ_s^′ (T) + 2. A similar result for Δ = 3 was established by Lih and Liu [21].
Keywords: strong edge-coloring, strong chromatic index, Halin graphs 
@article{DMGT_2018_38_1_a0,
     author = {Hu, Ziyu and Lih, Ko-Wei and Liu, Daphne Der-Fen},
     title = {Upper {Bounds} for the {Strong} {Chromatic} {Index} of {Halin} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--26},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a0/}
}
TY  - JOUR
AU  - Hu, Ziyu
AU  - Lih, Ko-Wei
AU  - Liu, Daphne Der-Fen
TI  - Upper Bounds for the Strong Chromatic Index of Halin Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 5
EP  - 26
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a0/
LA  - en
ID  - DMGT_2018_38_1_a0
ER  - 
%0 Journal Article
%A Hu, Ziyu
%A Lih, Ko-Wei
%A Liu, Daphne Der-Fen
%T Upper Bounds for the Strong Chromatic Index of Halin Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 5-26
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a0/
%G en
%F DMGT_2018_38_1_a0
Hu, Ziyu; Lih, Ko-Wei; Liu, Daphne Der-Fen. Upper Bounds for the Strong Chromatic Index of Halin Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 5-26. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a0/

[1] L.D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math. 108 (1992) 231–252. doi:10.1016/0012-365X(92)90678-9

[2] J. Bensmail, A. Harutyunyan, H. Hocquard and P. Valicov, Strong edge-coloring of sparse planar graphs, Discrete Appl. Math. 179 (2014) 229–234. doi:10.1016/j.dam.2014.07.006

[3] O.V. Borodin and A.O. Ivanova, Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory 33 (2013) 759–770. doi:10.7151/dmgt.1708

[4] H. Bruhn and F. Joos, A stronger bound for the strong chromatic index, Electron. Notes Discrete Math. 49 (2015) 277–284. doi:10.1016/j.endm.2015.06.038

[5] G.J. Chang and G.-H. Duh, On the precise value of the strong chromatic-index of a planar graph with a large girth . arXiv: 1508.03052

[6] G.J. Chang and D. Liu, Strong edge-coloring for cubic Halin graphs, Discrete Math. 312 (2012) 1468–1475. doi:10.1016/j.disc.2012.01.014

[7] G.J. Chang, M. Montassier, A. Pêcher and A. Raspaud, Strong chromatic index of planar graphs with large girth, Discuss. Math. Graph Theory 34 (2014) 723–733. doi:10.7151/dmgt.1763

[8] D.W. Cranston, Strong edge-coloring of graphs with maximum degree 4 using 22 colors, Discrete Math. 306 (2006) 2772–2778. doi:10.1016/j.disc.2006.03.053

[9] P. DeOrsey, J. Diemunsch, M. Ferrara, N. Graber, S.G. Hartke, S. Jahanbekam, B. Lidicky, L.L. Nelsen, D. Stolee and E. Sullivan, On the strong chromatic index of sparse graphs . arXiv: 1508.03515

[10] P. Erdős, Problems and results in combinatorial analysis and graph theory, Discrete Math. 72 (1988) 81–92. doi:10.1016/0012-365X(88)90196-3

[11] P. Erdős and J. Nešetřil, Problem, in: Irregularities of Partitions, G. Halász and V.T. Sós (Eds.) (Springer, Berlin, 1989) 162–163.

[12] R.J. Faudree, R.H. Schelp, A. Gyárfás and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211.

[13] J.L. Fouquet and J. Jolivet, Strong edge-coloring of graphs and applications to multi-k-gons, Ars Combin. 16A (1983) 141–150.

[14] J.L. Fouquet and J. Jolivet, Strong edge-coloring of cubic planar graphs, Progress in Graph Theory in: J.A. Bondy and U.S.R. Murty (Ed(s)), (Academic Press, Toronto, 1984) 247–264.

[15] M.C. Golumbic and M. Lewenstein, New results on induced matchings, Discrete Appl. Math. 101 (2000) 157–165. doi:10.1016/S0166-218X(99)00194-8

[16] H. Hocquard, M. Montassier, A. Raspaud and P. Valicov, On strong edge-colouring of subcubic graphs, Discrete Appl. Math. 161 (2013) 2467–2479. doi:10.1016/j.dam.2013.05.021

[17] P. Horák, The strong chromatic index of graphs with maximum degree four, in: R. Bodendiek and K. Wagner (Ed(s)), Contemporary Methods in Graph Theory (BI Wissenschaft-Verlag, Mannheim, 1990) 399–403.

[18] P. Horák, H. Qing and W.T. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993) 151–160. doi:10.1002/jgt.3190170204

[19] D. Hudák, B. Lužar, R. Soták and R. Škrekovski, Strong edge-coloring of planar graphs, Discrete Math. 324 (2014) 41–49. doi:10.1016/j.disc.2014.02.002

[20] H.-H. Lai, K.-W. Lih and P.-Y. Tsai, The strong chromatic index of Halin graphs, Discrete Math. 312 (2012) 1536–1541. doi:10.1016/j.disc.2011.09.016

[21] K.-W. Lih and D.D.-F. Liu, On the strong chromatic index of cubic Halin graphs, Appl. Math. Lett. 25 (2012) 898–901. doi:10.1016/j.aml.2011.10.046

[22] M. Molloy and B. Reed, A bound on the strong chromatic index of a graph, J. Combin. Theory Ser. B 69 (1997) 103–109. doi:10.1006/jctb.1997.1724

[23] W.C. Shiu, P.C.B. Lam and W.K. Tam, On strong chromatic index of Halin graphs, J. Combin. Math. Combin. Comput. 57 (2006) 211–222.

[24] W.C. Shiu and W.K. Tam, The strong chromatic index of complete cubic Halin graphs, Appl. Math. Lett. 22 (2009) 754–758. doi:10.1016/j.aml.2008.08.019

[25] J. Wu and W. Lin, The strong chromatic index of a class of graphs, Discrete Math. 308 (2008) 6254–6261. doi:10.1016/j.disc.2007.11.051