Strong chromatic index of \(K_4\)-minor free graphs. (English) Zbl 1420.05063
Summary: The strong chromatic index \(\chi^\prime_s(G)\) of a graph \(G\) is the smallest integer \(k\) such that \(G\) has a proper edge \(k\)-colouring with the condition that any two edges at distance at most 2 receive distinct colours. In this paper, we prove that if \(G\) is a \(K_4\)-minor free graph with maximum degree \(\Delta\geq 3\), then \(\chi^\prime_s(G)\leq 3\Delta-2\). The result is best possible in the sense that there exist \(K_4\)-minor free graphs \(G\) with maximum degree \(\Delta\) such that \(\chi^\prime_s(G)=3\Delta-2\) for any given integer \(\Delta\geq 3\).
Keywords:
\(K_4\)-minor free graph; strong edge colouring; strong chromatic index; combinatorial problemsReferences:
| [1] | Andersen, L. D., The strong chromatic index of a cubic graph is at most 10, Discrete Math., 108, 231-252 (1992) · Zbl 0756.05050 |
| [2] | Appel, K.; Haken, W., Every planar graph map is four colourable, Bull. Am. Math. Soc., 82, 711-712 (1976) · Zbl 0331.05106 |
| [3] | Basavaraju, M.; Francis, M. C., Strong chromatic index of chordless graphs, J. Graph Theory, 80, 58-68 (2015) · Zbl 1321.05072 |
| [4] | Bruhn, H.; Joos, F., A stronger bound for the strong chromatic index, Electron. Notes Discrete Math., 49, 277-284 (2015) · Zbl 1346.05061 |
| [5] | Chang, G. J.; Narayanan, N., Strong chromatic index of 2-degenerate graphs, J. Graph Theory, 73, 119-126 (2013) · Zbl 1264.05047 |
| [6] | Chartrand, G.; Harary, F., Planar permutation graphs, Ann. Inst. Henri Poincaré Sect. B (N.S.), 3, 433-438 (1967) · Zbl 0162.27605 |
| [7] | Cranston, D. W., Strong edge-colouring of graphs with maximum degree 4 using 22 colours, Discrete Math., 306, 2772-2778 (2006) · Zbl 1143.05025 |
| [8] | Dȩbski, M.; Grytczuk, J.; Śleszyńska-Nowak, M., The strong chromatic index of sparse graphs, Inf. Process. Lett., 115, 326-330 (2015) · Zbl 1304.05043 |
| [9] | Duffin, J., Topology of series-parallel networks, J. Math. Anal. Appl., 10, 303-318 (1965) · Zbl 0128.37002 |
| [10] | Faudree, R. J.; Gyárfás, A.; Schelp, R. H.; Tuza, Zs., The strong chromatic index of graphs, Ars Comb., 29, B, 205-211 (1990) · Zbl 0721.05018 |
| [11] | Fouquet, J. L.; Jolivet, J. L., Strong edge-colourings of graphs and applications to multi-\(k\)-gons, Ars Comb., 16, A, 141-150 (1983) · Zbl 0536.05027 |
| [12] | Hocquard, H.; Ochem, P.; Valicov, P., Strong edge-colouring and induced matchings, Inf. Process. Lett., 113, 836-843 (2013) · Zbl 1284.68281 |
| [13] | Horák, P.; He, Q.; Trotter, W. T., Induced matchings in cubic graphs, J. Graph Theory, 17, 151-160 (1993) · Zbl 0787.05038 |
| [14] | Hudák, D.; Lužar, B.; Soták, R.; Škrekovski, R., Strong edge-colouring of planar graphs, Discrete Math., 324, 41-49 (2014) · Zbl 1284.05101 |
| [15] | Kostochka, A. V.; Li, X.; Ruksasakchai, W.; Santana, M.; Wang, T.; Yu, G., Strong chromatic index of subcubic planar multigraphs, Eur. J. Comb., 51, 380-397 (2016) · Zbl 1321.05123 |
| [16] | Lih, K.-W.; Wang, W.; Zhu, X., Colouring the square of a \(K_4\)-minor free graph, Discrete Math., 269, 303-309 (2003) · Zbl 1027.05042 |
| [17] | Molloy, M.; Reed, B., A bound on the strong chromatic index of a graph, J. Comb. Theory, Ser. B, 69, 103-109 (1997) · Zbl 0880.05036 |
| [18] | Wang, T., Strong chromatic index of \(k\)-degenerate graphs, Discrete Math., 330, 17-19 (2014) · Zbl 1295.05111 |
| [19] | Vizing, V. G., On an estimate of the chromatic index of a \(p\)-graph, Diskretn. Anal., 3, 25-30 (1964) · Zbl 1539.05042 |
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.
