×

On strong edge-coloring of claw-free subcubic graphs. (English) Zbl 1485.05065

Summary: A strong edge-coloring of a graph \(G\) is a proper edge coloring such that every path of length 3 uses three different colors. The strong chromatic index of \(G\), denoted by \(\chi_s^{\prime}(G)\), is the least possible number of colors in a strong edge-coloring of \(G\). In this paper, we prove that if \(G\) is a claw-free subcubic graph other than the prism graph, then \(\chi_s^{\prime}(G)\le 8\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C07 Vertex degrees
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersen, L., The strong chromatic index of a cubic graph is at most \(10\), Discrete Math., 108, 231-252 (1992) · Zbl 0756.05050 · doi:10.1016/0012-365X(92)90678-9
[2] Bonamy, M., Perrett, T., Postle, L.: Colouring graphs with sparse neighbourhoods: bounds and applications, arXiv:abs/1810.06704
[3] Bruhn, H.; Joos, F., A stronger bound for the strong chromatic index, Electronic Notes Discrete Math., 49, 277-284 (2015) · Zbl 1346.05061 · doi:10.1016/j.endm.2015.06.038
[4] Dȩbski, M.; Junosza-Szaniawski, K.; Śleszyńska-Nowak, M., Strong chromatic index of \(K_{1, t}\)-free graphs, Discrete Appl. Math., 284, 53-60 (2020) · Zbl 1443.05065 · doi:10.1016/j.dam.2020.03.024
[5] Erdös, P., Problems and results in combinatorial analysis and graph theory, Discrete Math., 72, 81-92 (1988) · Zbl 0661.05037 · doi:10.1016/0012-365X(88)90196-3
[6] Fouquet, J.; Jolivet, J., Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin., 16, 141-150 (1983) · Zbl 0536.05027
[7] Fouquet, J., Jolivet, J.: Strong edge-coloring of cubic planar graphs, Progress in Graph Theory, 247-264 (1984) · Zbl 0554.05022
[8] Hurley, E., de Joannis de Verclos, R., Kang, R.: An improved procedure for colouring graphs of bounded local density, arXiv:abs/2007.07874
[9] Hall, P., On representatives of subsetes, J. Lond. Math. Soc., 10, 26-30 (1935) · JFM 61.0067.01 · doi:10.1112/jlms/s1-10.37.26
[10] Horák, P.; Qing, H.; Trotter, W., Induced matchings in cubic graphs, J. Graph Theory, 17, 151-160 (1993) · Zbl 0787.05038 · doi:10.1002/jgt.3190170204
[11] Huang, M.; Santana, M.; Yu, G., Strong chromatic index of graphs with maximum degree four, Electronic J. Combin., 25, 1-24 (2018) · Zbl 1395.05057
[12] Lv, J-B; Li, X.; Yu, G., On strong edge-coloring of graphs with maximum degree 4, Discrete Appl. Math., 235, 142-153 (2018) · Zbl 1375.05099 · doi:10.1016/j.dam.2017.09.006
[13] Molloy, M.; Reed, B., A bound on the strong chromatic index of a graph, J. Combin. Theory Ser. B, 69, 519-530 (1997) · Zbl 0880.05036 · doi:10.1006/jctb.1997.1724
[14] Nandagopal, T., Kim, T., Gao, X., Barghavan, V.: Achieving MAC layer fairness in wireless packet networks, in: Proc. 6th ACM Conf. on Mobile Computing and Networking, pp. 87-98 (2000)
[15] Ramanathan, S.: A unified framework and algorithm for (T/F/C) DMA channel assignment in wireless networks, In: Proc. IEEE INFOCOM’97: 900-907 (1997)
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.