Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Injective Chromatic Index of \(K_4\)-Minor Free Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

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)\ge 3\) satisfies \(\chi ^\prime _{inj}(G)\le 2\Delta (G)+1\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Bondy, J. A., Murty, U. S. R.: Graph Theory, Springer (2008)

  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)

    Article  MathSciNet  Google Scholar 

  4. Bu, Y., Wang, P., Zhu, H., Zhu, J.: injective chromatic index of sparse graphs. Discret. Appl. Math. 345, 9–16 (2024)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  6. Dirac, G.: A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc. 27, 85–92 (1952)

    Article  MathSciNet  Google Scholar 

  7. Erdős, P., Rubin, A., Taylor, H.: Choosability graphs. Proc. West Coast Conf. Comb. Gr. Theory Comput. Congr. Numer. XXVI, 125–157 (1979)

    Google Scholar 

  8. Ferdjallah, B., Kerdjoudj, S., Raspaud, A.: Injective edge-coloring of subcubic graphs. Discrete Math. Algorithm. Appl. 14, 2250040 (2022)

    Article  MathSciNet  Google Scholar 

  9. Kostochka, A., Raspaud, A., Xu, J.: Injective edge-coloring of graphs with given maximum degree. Eur. J. Combin. 96, 103355 (2021)

    Article  MathSciNet  Google Scholar 

  10. Lu, J., Liu, H., Hu, X.: Injective edge coloring for graphs with small edge weight. Gr. Combin. 38, 160 (2022)

    Article  MathSciNet  Google Scholar 

  11. Lv, J.-B., Li, J., Zhou, N.: List injective edge-coloring of subcubic graphs. Discret. Appl. Math. 302, 163–170 (2021)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  13. Yang, W., Wu, B.: Injective edge-coloring of graphs with small weight. Gr. Combin. 38, 178 (2022)

    Article  MathSciNet  Google Scholar 

  14. Vizing, V.: Coloring the vertices of a graph with prescribed colours (in Russian). Metody Diskret. Analiz. 29, 3–10 (1976)

    Google Scholar 

  15. Zhu, J., Bu, Y., Zhu, H.: Injective edge coloring of sparse graphs with maximum degree 5. J. Comb. Optim. 45, 46 (2023)

    Article  MathSciNet  Google Scholar 

  16. Zhu, J.: Injective edge coloring of graphs with maximum degree \(5\). Discret. Appl. Math. 334, 119–126 (2023)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank referees for his/her careful reading of the paper and many constructive suggestions that improve the presentation of the paper greatly. This research was partially supported by the Key Laboratory of Mathematical Model and Application (Guangxi Normal University), Education Department of Guangxi Zhuang Autonomous Region.

Funding

Research of Jian-Bo Lv was supported by the Science and technology project of Guangxi (Guike AD21220114); NSFC (12301436). Research of Jianxi Li was supported by NSFC (12171089); NSF of Fujian (2021J02048).

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics and The Center for Applied Mathematics of Guangxi, Guangxi Normal University, Guilin, 541004, People’s Republic of China

    Jian-Bo Lv & Jiacong Fu

  2. School of Mathematics and Statistics, Minnan Normal University, Zhangzhou, 363000, People’s Republic of China

    Jianxi Li

Authors
  1. Jian-Bo Lv
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jiacong Fu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jianxi Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jian-Bo Lv.

Ethics declarations

Confict of Interest

The authors declare that they have no known competing financial interests or personal relationship that could have appeared to influence the work reported in this paper.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lv, JB., Fu, J. & Li, J. Injective Chromatic Index of \(K_4\)-Minor Free Graphs. Graphs and Combinatorics 40, 77 (2024). https://doi.org/10.1007/s00373-024-02807-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-024-02807-3

Keywords

AMS Classification:

Search

Navigation