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

The Chromatic Number of a Graph with Two Odd Holes and an Odd Girth

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

Abstract

An odd hole is an induced odd cycle of length at least five. Let \(\ell \ge 2\) be an integer, and let \({\mathcal {G}}_\ell \) denote the family of graphs which have girth \(2\ell + 1\) and have no holes of odd length at least \(2\ell +5\). In this paper, we prove that every graph \(G \in \cup _{\ell \ge 3}{\mathcal {G}}_\ell \) is 4-colourable.

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

Data Availability

Data sharing not applicable to this paper as no datasets were generated or analysed during the current study.

References

  1. Bondy, J., Murty, U.: Graph theory. In: GTM, vol. 244, Springer, Berlin (2008)

  2. Chudnovsky, M., Seymour, P.: Proof of a conjecture of Plummer and Zha. J. Graph Theory 1–14 (2023)

  3. Lan, K., Liu, F., Zhou, Y.: A note on a conjecture of Wu, Xu and Xu. Discret. Appl. Math. 326, 33–36 (2023)

    Article  MathSciNet  Google Scholar 

  4. Nelson, D., Plummer, M., Robertson, N., Zha, X.: On a conjecture concerning the Petersen graph. Electron. J. Combin. 18, 20 (2011)

    Article  MathSciNet  Google Scholar 

  5. Plummer, M., Zha, X.: On a conjecture concerning the Petersen graph: part II. Electron. J. Combin. 21, 1–34 (2014)

    Article  MathSciNet  Google Scholar 

  6. West, D.: Introduction to Graph Theory. Prentice Hall Inc., Hoboken (1996)

    Google Scholar 

  7. Wu, D., Xu, B., Xu, Y.: On coloring of graphs of girth \(2\ell +1\) without longer odd holes (in Chinese). Sci. China Math. 53, 103–120 (2023)

    Google Scholar 

  8. Wu, D., Xu, B., Xu, Y.: The chromatic number of heptagraphs. arXiv:2206.01400 (2022)

  9. Xu, B., Yu, G., Zha, X.: A note on chromatic number and induced odd cycles. Electron. J. Combin. 24(4), 4–32 (2017)

    Article  MathSciNet  Google Scholar 

  10. Xu, Y.: On the structure of pentagraphs. Appl. Math. Comput. 439, 127632 (2023)

    MathSciNet  Google Scholar 

Download references

Acknowledgements

We would like to thank the anonymous referee for his/her careful reading and valuable suggestions. We also would like to thanks Yidong Zhou for inspiring discussions on this subject.

Funding

This research was supported by the NSFC grant 12271170 and Science and Technology Commission of Shanghai Municipality (STCSM) grant 22DZ2229014.

Author information

Authors and Affiliations

  1. Center for Discrete Mathematics, Fuzhou University, Fujian, 350003, China

    Kaiyang Lan

  2. Department of Mathematics, East China Normal University, Shanghai, 200241, China

    Feng Liu

Authors
  1. Kaiyang Lan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Feng Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Feng Liu.

Ethics declarations

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships 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

Lan, K., Liu, F. The Chromatic Number of a Graph with Two Odd Holes and an Odd Girth. Graphs and Combinatorics 39, 125 (2023). https://doi.org/10.1007/s00373-023-02723-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-023-02723-y

Keywords

Mathematics Subject Classification

Search

Navigation