Article in press
Authors:
Title:
Strong chromatic index of claw-free graphs with edge weight seven
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-01-13 , Revised: 2023-04-13 , Accepted: 2023-04-13 , Available online: 2023-05-01 , https://doi.org/10.7151/dmgt.2497
Abstract:
Let $G$ be a graph and $k$ a positive integer. A strong $k$-edge-coloring of $G$
is a mapping $\phi: E(G)\to \{1,2,\dots,k\}$ such that for any two edges $e$ and
$e'$ that are either adjacent to each other or adjacent to a common edge,
$\phi(e)\neq \phi(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\in 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.
Keywords:
strong edge coloring, strong chromatic index, claw-free graph, edge weight
References:
- 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 - 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 - 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 - 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 - M. Dębski, K. Junosza-Szaniawski and M. Śleszyńska-Nowak, Strong chromatic index of $K_{1,t}$-free graphs, Discrete Appl. Math. 284 (2020) 53–60.
https://doi.org/10.1016/j.dam.2020.03.024 - 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 - 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 - J.L. Fouquet and J.L. Jolivet, Strong edge-colorings of graphs and applications to multi-$k$-gons, Ars Combin. 16A (1983) 141–150.
- 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 - P. Horák, The strong chromatic index of graphs with maximum degree four, Contemp. Methods Graph Theory (1990) 399–403.
- 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 - 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 - Y. Lin and W. Lin, The tight bound for the strong chromatic indices of claw-free subcubic graphs (2022).
arXiv: 2207.10264 - 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 - 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 - 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 - 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 - C. Zang, The strong chromatic index of graphs with maximum degree $\Delta$ (2015).
arXiv: 1510.00785
Close