Injective edge coloring of planar graphs without short cycles

Expand
  • 1. College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
    2. Xingzhi College, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
    3. College of Data Science, Jiaxing University, Jiaxing 314001, Zhejiang, China

Received date: 2021-03-19

  Online published: 2024-12-20

Copyright

, 2024, All rights reserved, without authorization

Abstract

To explore radio network packaging issues, Cardoso et al. proposed the concept of injective edge coloring of a graph in 2015. A $k$-injective edge coloring of $G$ is a coloring of the edges of $G, f$: $E(G)\to C=\{1,2,\cdots,k\}$, such that if $e_{1},\ e_{2},\ e_{3}$ are three consecutive edges in $G$, then $f(e_{1})\neq f(e_{3})$, where $e_{1},\ e_{2}$ and $e_{3}$ are consecutive if they form a path or a cycle of length 3. The injective edge coloring number, denoted by $\chi'_{i}(G)$, is the minimum number of colors such that $G$ has such a coloring. In this paper, we use minimal counter example and power transfer method to prove that if $G$ is a planar graph without $k$-cycles and $4^{-}$-cycles disjoint, then $\chi'_{i}(G)\leq3\Delta(G)-2$, where $5\leq k\leq10$.

Cite this article

Yuehua BU, Wenwen CHEN, Junlei ZHU . Injective edge coloring of planar graphs without short cycles[J]. Operations Research Transactions, 2024 , 28(4) : 143 -151 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.014

References

1 Hahn G , Kratochvíl J , Sirá J , et al. On the injective chromatic number of graphs[J]. Discrete Mathematics, 2002, 256 (1/2): 179- 192.
2 Cardoso D M , Cruz J P , Cerdeira J O , et al. Injective edge coloring of graphs[J]. Filomat, 2020, 33 (19): 6411- 6423.
3 Bu Y H , Qi C T . Injective edge coloring of sparse graphs[J]. Discrete Mathematics, Algorithms and Applications, 2018, 10 (2): 1- 16.
4 Baya F, Samia K, André R. Induced star arboricity and injective edge-coloring of graphs[EB/OL]. (2020-08-31)[2021-01-02]. arXiv: 1907.09838.
5 卜月华, 齐晨涛, 朱俊蕾. 平面图的单射边染色[J]. 数学进展, 2020, 49 (6): 675- 684.
6 Kostochka A , Raspaud A , Xu J W . Injective edge-coloring of graphs with given maximun degree[J]. European Jounal of Combinatorics, 2021, 96, 1- 12.
Outlines

/