×

Strong edge-coloring for planar graphs with large girth. (English) Zbl 1400.05081

Summary: A strong edge-coloring of a graph \(G = (V, E)\) is a partition of its edge set \(E\) into induced matchings. Let \(G\) be a connected planar graph with girth \(k \geq 26\) and maximum degree \(\varDelta\). We show that either \(G\) is isomorphic to a subgraph of a very special \(\varDelta\)-regular graph with girth \(k\), or \(G\) has a strong edge-coloring using at most \(2 \varDelta + \lceil \frac{12(\varDelta - 2)}{k} \rceil\) colors.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bensmail, J.; Haratyunyan, A.; Hocquard, H.; Valicov, P., Strong edge-coloring of sparse planar graphs, Discrete Appl. Math., 179, 229-234, (2014) · Zbl 1303.05057
[2] Borodin, O. V.; Ivanova, A. O., Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33, 759-770, (2013) · Zbl 1301.05118
[3] G.H. Chang, G.H. Duh, On the precise value of the strong chromatic index of a planar graph with a large girth, arXiv:1508.03052; G.H. Chang, G.H. Duh, On the precise value of the strong chromatic index of a planar graph with a large girth, arXiv:1508.03052 · Zbl 1394.05031
[4] Chang, G. J.; Montassier, M.; Pêcher, A.; Raspaud, A., Strong chromatic index of planar graphs with large girth, Discuss. Math. Graph Theory, 34, 723-733, (2014) · Zbl 1303.05063
[5] 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
[6] Fouquet, J. L.; Jolivet, J. L., Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin., 16A, 141-150, (1983) · Zbl 0536.05027
[7] Hudák, D.; Luz̆ar, B.; Soták, R.; S̆krekovski, R., Strong edge-coloring of planar graphs, Discrete Math., 324, 41-49, (2014) · Zbl 1284.05101
[8] Kostochka, A. V.; Li, X.; Ruksasakchai, W.; Santana, M.; Wang, T.; Yu, G., Strong chromatic index of subcubic planar multigraphs, European J. Combin., 51, 380-397, (2016) · Zbl 1321.05123
[9] W. Ruksasakchai, T. Wang, Strong edge-coloring of planar graphs with girth at least six, arXiv:1402.5677; W. Ruksasakchai, T. Wang, Strong edge-coloring of planar graphs with girth at least six, arXiv:1402.5677 · Zbl 1375.05106
[10] Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Metody Diskret. Analiz, 3, 25-30, (1964)
[11] T. Wang, X. Zhao, Odd graphs and its application on the strong edge-coloring, arXiv:1412.8358v3; T. Wang, X. Zhao, Odd graphs and its application on the strong edge-coloring, arXiv:1412.8358v3
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.