×

Injective edge-coloring of graphs with small weight. (English) Zbl 1502.05077

Summary: The edge weight, denoted by \(\Delta_e(G)\), of a graph \(G\) is max \(\{d_G(u)+d_G(v):uv\in E(G)\}\). An edge-coloring of a graph \(G\) is injective if for any two distinct edges \(e_1\) and \(e_2\), the colors of \(e_1\) and \(e_2\) are distinct if they are at distance 2 in \(G\) or in a common triangle. The injective chromatic index of \(G\), denoted by \(\chi_i^\prime(G)\), is the minimum number of colors needed for an injective edge-coloring of \(G\). B. Ferdjallah et al. [“Injective edge-coloring of sparse graphs”, Preprint, arXiv:1907.09838] posed a conjecture which says that if \(G\) is subcubic graph, then \(\chi_i^\prime(G) \le 6\). A. Kostochka et al. [Eur. J. Comb. 96, Article ID 103355, 12 p. (2021; Zbl 1466.05072)] showed that if \(G\) is a subcubic graph, then \(\chi_i^\prime(G) \le 7\). We extend the above result by showing that \[ \chi^\prime_i(G)\le \begin{cases} 4, & \quad{\text{ if } \Delta_e(G)\le 5,}\\ 7, & \quad{\text{ if } \Delta_e(G)\le 6,}\\ 12, & \quad{\text{ if } \Delta_e(G)\le 7}. \end{cases} \] In addition, we prove that \(\chi_i^\prime(G) \le 6\) for any subcubic claw-free graph, and this bound is sharp.

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1466.05072
Full Text: DOI

References:

[1] Axenovich, M.; Dörr, P.; Rollin, J.; Ueckerdt, T., Induced and weak induced arboricities, Discrete Math., 342, 511-519 (2019) · Zbl 1400.05179 · doi:10.1016/j.disc.2018.10.018
[2] Bondy, J.A., Murty, U.S.R.: Graph Theory, Graduate Text in Mathematics, vol. 244. Springer, New York (2008) · Zbl 1134.05001
[3] Bu, Y.; Qi, C., Injective edge coloring of sparse graphs, Discrete Math. Algorithms Appl., 10, 2, 18502022 (2018) · Zbl 1383.05094 · doi:10.1142/S1793830918500222
[4] Cardoso, DM; Cerdeira, JO; Cruz, JP; Dominic, C., Injective coloring of graphs, Filomat, 33, 19, 6411-6423 (2019) · Zbl 1499.05206 · doi:10.2298/FIL1919411C
[5] Chen, L.; Huang, M.; Yu, G.; Zhou, X., The strong edge-coloring for graphs with small edge weight, Discrete Math., 343, 111779 (2020) · Zbl 1433.05113 · doi:10.1016/j.disc.2019.111779
[6] Chen, L.; Chen, S.; Zhao, R.; Zhou, X., The strong chromatic index of graphs with edge weight eight, J. Combin. Optim., 40, 227-233 (2020) · Zbl 1445.05038 · doi:10.1007/s10878-020-00582-4
[7] Erdős, P., Lovász, L.: Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets (Colloq. Keszthely, 1973; Dedicated to P. Erdős on His 60th Birthday), Vol. II. In: Colloq. Math. Soc. János Bolyai, vol. 10. North-Holland, Amsterdam, pp. 609-627 (1975) · Zbl 0315.05117
[8] Ferdjallah, B., Kerdjoudj, S., Raspaud, A.: Injective edge-coloring of sparse graphs (2019). arXiv:1907.09838
[9] Hall, P., On representatives of subsets, J. Lond. Math. Soc., 10, 26-30 (1935) · JFM 61.0067.01 · doi:10.1112/jlms/s1-10.37.26
[10] Kostochka, A.; Raspaud, A.; Xu, J., Injective edge-coloring of graphs with given maximum degree, Eur. J. Combin., 96, 103355 (2021) · Zbl 1466.05072 · doi:10.1016/j.ejc.2021.103355
[11] Lv, J.; Li, J.; Zhou, N., List injective edge-coloring of subcubic graphs, Discrete Appl. Math., 302, 163-170 (2021) · Zbl 1470.05061 · doi:10.1016/j.dam.2021.07.010
[12] Miao, Z.; Song, Y.; Yu, G., Note on injective edge-coloring of graphs, Discrete Appl. Math., 310, 65-74 (2022) · Zbl 1482.05118 · doi:10.1016/j.dam.2021.12.021
[13] Wu, J.; Lin, W., The strong chromatic index of a class of graphs, Discrete Math., 308, 6254-6261 (2008) · Zbl 1214.05033 · doi:10.1016/j.disc.2007.11.051
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.