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

List Injective Coloring of Planar Graphs

  • Published:
Acta Mathematicae Applicatae Sinica, English Series Aims and scope Submit manuscript

Abstract

A k-coloring of a graph G is a mapping c: V(G) → {1, 2, ⋯, k}. The coloring c is called injective if any two vertices have a common neighbor get distinct colors. A graph G is injectively k-choosable if for any color list L of admissible colors on V(G) of size k allows an injective coloring φ such that φ(v) ∈ L(v) for each v ∈ V(G). Let χi(G), χ li (G) denote the injective chromatic number and injective choosability number of G, respectively. In this paper, we show that χ li (G) ≤ Δ + 4 if Δ ≥ 22 and χ li (G) ≤ Δ + 5 if Δ ≥ 15, where G is a triangle-free planar graph and without intersecting 4-cycles.

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

Similar content being viewed by others

References

  1. Bondy, J.A., Murty, U.S.R. Graph Theory. Macmillan Ltd. Springer, 2008

    Book  Google Scholar 

  2. Borodin, O.V., Ivanova, A.O. List injective colorings of planar graphs. Discret Mathematics, 311: 154–165 (2011)

    Article  MathSciNet  Google Scholar 

  3. Bu, Y., Huang, C. List injective coloring of a class of planar graphs without short cycles. Discrete Mathematics Algorithms and Applications, 10: 663–672 (2018)

    MathSciNet  MATH  Google Scholar 

  4. Bu, Y., Qi, C., Zhu, J., Xu, T. Injective coloring of planar graphs. Theoretical Computer Science, 857: 114–122 (2021)

    Article  MathSciNet  Google Scholar 

  5. Bu, Y., Yang, S. List injective coloring of planar graph with girth g ≥ 5. Discrete Mathematics, Algorithms and Applications, 6: 1450006 (2014)

    Article  MathSciNet  Google Scholar 

  6. Cai, J., Wang, J., Zhang, X. Restricted coloirngs of graphs. Science Press, Beijing, 2019

    Google Scholar 

  7. Chen, H., Wu, J. List injective coloring of planar graphs with girth g ≥ 6. Discrete Mathematics, 339: 3043–3051 (2016)

    Article  MathSciNet  Google Scholar 

  8. Chen, M., Hahn, G., Raspaud, A., Wang, W. Some results om the injective chromatic number of graphs. Journal of Combinatorial Optimization, 24: 299–318 (2012)

    Article  MathSciNet  Google Scholar 

  9. Cranston, D.W., Kim, S.-J., Yu, G. Injective colorings of planar graphs with low average degree. Algorithmica, 60: 553–568 (2010)

    Article  Google Scholar 

  10. Cranston, D.W., Kim, S.-J., Yu, G. Injective colorings of sparse graphs. Discrete Mathematics, 310: 2965–2973 (2010)

    Article  MathSciNet  Google Scholar 

  11. Doyon, A., Hahn, G., Raspaud, A. Some bounds on the injective chromatics number of graphs. Discrete Mathematics, 310: 585–590 (2010)

    Article  MathSciNet  Google Scholar 

  12. Dong, W., Lin, W. Injective coloring of planar graphs with girth 6. Discrete Mathematics, 313: 1302–1311 (2013)

    Article  MathSciNet  Google Scholar 

  13. Dong, W., Lin, W. Injective coloring of plane graphs with girth 5. Discrete Mathematics, 315: 120–127 (2014)

    Article  MathSciNet  Google Scholar 

  14. Hahn, G., Kratochvrl, J., Sotteau, D., Sirán, J. On the injective chromatic number of graphs. Discrete Mathematics, 256: 179–192 (2002)

    Article  MathSciNet  Google Scholar 

  15. Li, R., Xu, B. Injective choosability of planar graphs of girth five and six. Discrete Mathematics, 312: 1260–1265 (2012)

    Article  MathSciNet  Google Scholar 

  16. Lužar, B. Planar graphs with largest injective chromatic number. IMFM Preprint Series, 48: 9–11 (2010)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Shandong Normal University, Jinan, 250358, China

    Wen-wen Li

  2. School of Mathematics and Information Sciences, Weifang University, Weifang, 261061, China

    Jian-sheng Cai

  3. Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing, 100190, China

    Gui-ying Yan

Authors
  1. Wen-wen Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jian-sheng Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gui-ying Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jian-sheng Cai.

Additional information

This paper is supported by the National Natural Science Foundation of China (Nos. 12071351,11571258).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, Ww., Cai, Js. & Yan, Gy. List Injective Coloring of Planar Graphs. Acta Math. Appl. Sin. Engl. Ser. 38, 614–626 (2022). https://doi.org/10.1007/s10255-022-1103-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10255-022-1103-7

Keywords

2000 MR Subject Classification

Search

Navigation