[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Acyclic coloring of graphs with some girth restriction

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

A vertex coloring of a graph \(G\) is called acyclic if it is a proper vertex coloring such that every cycle \(C\) receives at least three colors. The acyclic chromatic number of \(G\) is the least number of colors in an acyclic coloring of \(G\). We prove that acyclic chromatic number of any graph \(G\) with maximum degree \(\Delta \ge 4\) and with girth at least \(4\Delta \) is at most \(12\Delta \).

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Alon N, McDiarmid C, Reed B (1991) Acyclic coloring of graphs. Random Struct Algorithms 2:277–288

    Article  MathSciNet  MATH  Google Scholar 

  • Bondy JA, Murty USR (1976) Graph theory with applications. Macmillan Press[M], New York

    Book  MATH  Google Scholar 

  • Gerke S, Raemy M (2007) Generalized acyclic edge coloings of graphs with large girth. Discret Math 307:1668–1671

    Article  MathSciNet  MATH  Google Scholar 

  • Goncalves D, Montassier M, Pinlou A. Entropy compression method applied to graph coloring, arXiv:1406.4380vl

  • Greenhill C, Pikhurko O (2005) Bounds on the generalized acyclic chromatic number of bounded degree graphs. Graphs Combin 21:407–419

    Article  MathSciNet  MATH  Google Scholar 

  • Grünbaum B (1973) Acyclic colorings of planar graphs. Israel J Math 14:390–408

    Article  MathSciNet  MATH  Google Scholar 

  • Molloy M, Reed B (2002) Graph coloring and the probabilistic method, algorithms and combinatorics. Springer, New York

    MATH  Google Scholar 

  • Molloy M, Reed B (1998) Further algorithmic aspects of Loász Local Lemma. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, p 524–529

Download references

Acknowledgments

We would like to thank the reviewers for providing some very helpful suggestions for revising this paper. This work is supported by NSFSD (ZR2013AM001, ZR2013AL016) and NSFC (11371355).

Author information

Authors and Affiliations

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

    Jiansheng Cai & Binlu Feng

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

    Guiying Yan

Authors
  1. Jiansheng Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Binlu Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Guiying Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jiansheng Cai.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cai, J., Feng, B. & Yan, G. Acyclic coloring of graphs with some girth restriction. J Comb Optim 31, 1399–1404 (2016). https://doi.org/10.1007/s10878-015-9829-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-015-9829-2

Keywords

Search

Navigation