Abstract
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\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andersen, L.: The strong chromatic index of a cubic graph is at most \(10\). Discrete Math. 108, 231–252 (1992)
Bonamy, M., Perrett, T., Postle, L.: Colouring graphs with sparse neighbourhoods: bounds and applications, arXiv:abs/1810.06704
Bruhn, H., Joos, F.: A stronger bound for the strong chromatic index. Electronic Notes Discrete Math. 49, 277–284 (2015)
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)
Erdös, P.: Problems and results in combinatorial analysis and graph theory. Discrete Math. 72, 81–92 (1988)
Fouquet, J., Jolivet, J.: Strong edge-colorings of graphs and applications to multi-k-gons. Ars Combin. 16, 141–150 (1983)
Fouquet, J., Jolivet, J.: Strong edge-coloring of cubic planar graphs, Progress in Graph Theory, 247–264 (1984)
Hurley, E., de Joannis de Verclos, R., Kang, R.: An improved procedure for colouring graphs of bounded local density, arXiv:abs/2007.07874
Hall, P.: On representatives of subsetes. J. Lond. Math. Soc. 10, 26–30 (1935)
Horák, P., Qing, H., Trotter, W.: Induced matchings in cubic graphs. J. Graph Theory 17, 151–160 (1993)
Huang, M., Santana, M., Yu, G.: Strong chromatic index of graphs with maximum degree four. Electronic J. Combin. 25, 1–24 (2018)
Lv, J.-B., Li, X., Yu, G.: On strong edge-coloring of graphs with maximum degree 4. Discrete Appl. Math. 235, 142–153 (2018)
Molloy, M., Reed, B.: A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B 69, 519–530 (1997)
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)
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)
Acknowledgements
Supported by the Institute of Meteorological Big Data-Digital Fujian and Fujian Key Laboratory of Data Science and Statistics.
Funding
Research of Jian-Bo Lv was supported by NSFC (No.12161010) and Youth Science Foundation of Guangxi (No.2019JJB110007). Research of Jianxi Li was supported by NSF of China (No.12171089) and NSF of Fujian (No.2021J02048). Research of Xiaoxia Zhang was supported by NSF of China (No.11701496).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Competing interests
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Research of Jian-Bo Lv was supported by NSFC (No.12161010) and Youth Science Foundation of Guangxi (No.2019JJB110007). Research of Jianxi Li was supported by NSF of China (No.12171089) and NSF of Fujian (No.2021J02048). Research of Xiaoxia Zhang was supported by NSF of China (No.11701496).
Rights and permissions
About this article
Cite this article
Lv, JB., Li, J. & Zhang, X. On Strong Edge-Coloring of Claw-Free Subcubic Graphs. Graphs and Combinatorics 38, 63 (2022). https://doi.org/10.1007/s00373-022-02462-6
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-022-02462-6