Injective edge-coloring of claw-free graphs with maximum degree 4

Danjun Huang, Yuqian Guo

Abstract


An injective k-edge-coloring of a graph G is a mapping ϕ : E(G) → {1, 2, …, k}, such that ϕ(e) ≠ ϕ(e′) if edges e and e′ are at distance two, or are in a triangle. The smallest integer k such that G has an injective k-edge-coloring is called the injective chromatic index of G, denoted by χ′i(G). A graph is called claw-free if it has no induced subgraph isomorphic to the complete bipartite graph K1,3. In this paper, we show that χ′i(G) ≤ 13 for every claw-free graph G with Δ(G) ≤ 4, where Δ(G) is the maximum degree of G.


Keywords


maximum degree; claw-free; injective edge-coloring

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.2.6

References

Y. Bu and C. Qi, Injective edge coloring of sparse graphs, Discrete Math. Algorithms Appl. 10 (2018) 1850022, 16 pp.

D. Cardoso, J. Cerdeira, J. Cruz, and C. Dominic, Injective edge coloring of graphs, Filomat 33 (2019), 6411–6423.

Q. Cui and Z. Han, Injective edge-coloring of claw-free subcubic graphs, J. Comb. Optim. 47 (2024) 87, 32 pp.

X. Dong, Y. Lin, and W. Lin, The injective chromatic index of a claw-free subcubic graph is at most 6, J. Math. Res. Appl. 43 (2023), 409–416.

B. Ferdjallah, S. Kerdjoudj, and A. Raspaud, Injective edge-coloring of subcubic graphs, Discrete Math. Algorithms Appl. 14 (2022) 2250040, 22 pp.

J. Fu and J. Lv, On injective edge-coloring of graphs with maximum degree 4, Discrete Appl. Math. 360 (2025), 119–130.

X. Hu and G. Zhang, Injective edge chromatic index of sparse graphs, Discrete Appl. Math. 370 (2025), 50–56.

A. Kostochka, A. Raspaud, and J. Xu, Injective edge-coloring of graphs with given maximum degree, European J. Combin. 96 (2021) 103355, 12 pp.

J. Lu and X. Pan, Injective edge coloring of some sparse graphs, J. Appl. Math. Comput. 69 (2023), 3421–3431.

Z. Miao, Y. Song, and G. Yu, Note on injective edge-coloring of graphs, Discrete Appl. Math. 310 (2022), 65–74.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats