Injective chromatic index of \(K_4\)-minor free graphs. (English) Zbl 07888732
Summary: 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\), \(\chi^\prime_{inj}(G)\), is the minimum number of colors needed for an injective edge-coloring of \(G\). In this note, we show that every \(K_4\)-minor free graph \(G\) with maximum degree \(\Delta (G) \geq 3\) satisfies \(\chi^\prime_{inj}(G) \leq 2\Delta (G)+1\).
References:
| [1] | Bondy, J. A., Murty, U. S. R.: Graph Theory, Springer (2008) · Zbl 1134.05001 |
| [2] | Bradshaw, P., Clow, A., Xu, J.: Injective edge coloring of degenerate graphs and the oriented chromatic number, arXiv:2308.15654v1 |
| [3] | Bu, Y.; Qi, C., Injective edge coloring of sparse graphs, Discret. Math. Algorithm. Appl., 10, 1850022, 2018 · Zbl 1383.05094 · doi:10.1142/S1793830918500222 |
| [4] | Bu, Y.; Wang, P.; Zhu, H.; Zhu, J., injective chromatic index of sparse graphs, Discret. Appl. Math., 345, 9-16, 2024 · Zbl 1531.05065 · doi:10.1016/j.dam.2023.11.027 |
| [5] | Cardoso, D.; Cerdeira, J.; Cruz, J.; Dominic, C., Injective edge coloring of graphs, Filomat, 19, 6411-6423, 2019 · Zbl 1499.05206 · doi:10.2298/FIL1919411C |
| [6] | Dirac, G., A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc., 27, 85-92, 1952 · Zbl 0046.41001 · doi:10.1112/jlms/s1-27.1.85 |
| [7] | Erdős, P.; Rubin, A.; Taylor, H., Choosability graphs, Proc. West Coast Conf. Comb. Gr. Theory Comput. Congr. Numer., XXVI, 125-157, 1979 · Zbl 0469.05032 |
| [8] | Ferdjallah, B.; Kerdjoudj, S.; Raspaud, A., Injective edge-coloring of subcubic graphs, Discrete Math. Algorithm. Appl., 14, 2250040, 2022 · Zbl 1516.05064 · doi:10.1142/S1793830922500409 |
| [9] | Kostochka, A.; Raspaud, A.; Xu, J., Injective edge-coloring of graphs with given maximum degree, Eur. J. Combin., 96, 2021 · Zbl 1466.05072 · doi:10.1016/j.ejc.2021.103355 |
| [10] | Lu, J.; Liu, H.; Hu, X., Injective edge coloring for graphs with small edge weight, Gr. Combin., 38, 160, 2022 · Zbl 1497.05094 · doi:10.1007/s00373-022-02562-3 |
| [11] | Lv, J-B; Li, J.; Zhou, N., List injective edge-coloring of subcubic graphs, Discret. 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, Discret. Appl. Math., 310, 65-74, 2022 · Zbl 1482.05118 · doi:10.1016/j.dam.2021.12.021 |
| [13] | Yang, W.; Wu, B., Injective edge-coloring of graphs with small weight, Gr. Combin., 38, 178, 2022 · Zbl 1502.05077 · doi:10.1007/s00373-022-02582-z |
| [14] | Vizing, V., Coloring the vertices of a graph with prescribed colours (in Russian), Metody Diskret. Analiz., 29, 3-10, 1976 · Zbl 0362.05060 |
| [15] | Zhu, J.; Bu, Y.; Zhu, H., Injective edge coloring of sparse graphs with maximum degree 5, J. Comb. Optim., 45, 46, 2023 · Zbl 1510.05090 · doi:10.1007/s10878-022-00972-w |
| [16] | Zhu, J., Injective edge coloring of graphs with maximum degree \(5\), Discret. Appl. Math., 334, 119-126, 2023 · Zbl 1512.05150 · doi:10.1016/j.dam.2023.03.022 |
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.
