Strong chromatic index of claw-free graphs with edge weight seven

Lin, Yuquan ; Lin, Wensong 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1311-1325

Résumé

Let G be a graph and k a positive integer. A strong k-edge-coloring of G is a mapping ϕ: E(G)→{1,2,...,k} such that for any two edges e and e^' that are either adjacent to each other or adjacent to a common edge, ϕ(e)ϕ(e^'). The strong chromatic index of G is the minimum integer k such that G has a strong k-edge-coloring. The edge weight of G is defined to be max{d(u)+d(v):uv∈ E(G)}, where d(v) denotes the degree of v in G. In this paper, we prove that every claw-free graph with edge weight at most 7 has strong chromatic index at most 9, which is sharp.

Détail

Keywords: strong edge coloring, strong chromatic index, claw-free graph, edge weight

Bibliographie

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

[2] L. Chen, S. Chen, R. Zhao and X. Zhou, The strong chromatic index of graphs with edge weight eight, J. Comb. Optim. 40 (2020) 227–233. https://doi.org/10.1007/s10878-020-00582-4

[3] L. Chen, M. Huang, G. Yu and X. Zhou, The strong edge-coloring for graphs with small edge weight, Discrete Math. 343(4) (2020) 111779. https://doi.org/10.1016/j.disc.2019.111779

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

[5] M. Dębski, K. Junosza-Szaniawski and M. Śleszyńska-Nowak, Strong chromatic index of K1,t-free graphs, Discrete Appl. Math. 284 (2020) 53–60. https://doi.org/10.1016/j.dam.2020.03.024

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

[7] P. Erdős and J. Nešetřil, Problem, in: Irregularities of Partitions, G. Halász and V.T. Sós (Ed(s)), (Springer, Berlin 1989) 161–165. https://doi.org/https://doi.org/10.1007/978-3-642-61324-1_15

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

[9] P. Hall, On representatives of subsets, J. Lond. Math. Soc. (1) 10 (1935) 26–30. https://doi.org/10.1112/jlms/s1-10.37.26

[10] P. Horák, The strong chromatic index of graphs with maximum degree four, Contemp. Methods Graph Theory (1990) 399–403.

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

[12] M. Huang, M. Santana and G. Yu, Strong chromatic index of graphs with maximum degree four, Electron. J. Combin. 25(3) (2018) #P3.31. https://doi.org/10.37236/7016

[13] Y. Lin and W. Lin, The tight bound for the strong chromatic indices of claw-free subcubic graphs (2022). arXiv: 2207.10264

[14] J.-B. Lv, J. Li and X. Zhang, On strong edge-coloring of claw-free subcubic graphs, Graphs Combin. 38(3) (2022) 63. https://doi.org/10.1007/s00373-022-02462-6

[15] T. Nandagopal, T. Kim, X. Gao and V. Bharghavan, Achieving MAC layer fairness in wireless packet networks, in: Proc. 6th Annual International Conference on Mobile Computing and Networking (2000) 87–98. https://doi.org/10.1145/345910.345925

[16] S. Ramanathan, A unified framework and algorithm for (T/F/C) DMA channel assignment in wireless networks, in: Proc.16th Annual Joint Conference of the IEEE Computer and Communications Societies 2 (1997) 900–907. https://doi.org/10.1109/INFCOM.1997.644573

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

[18] C. Zang, The strong chromatic index of graphs with maximum degree \Delta (2015). arXiv: 1510.00785