Acyclic Edge Coloring of Planar Graphs Without Small Cycles | Graphs and Combinatorics Skip to main content
Log in

Acyclic Edge Coloring of Planar Graphs Without Small Cycles

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

Abstract

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ≤ Δ(G) + 2 for any graphs. In this paper, it is shown that the conjecture holds for planar graphs without 4- and 5-cycles or without 4- and 6-cycles.

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

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Alon N.: A parallel algorithmic version of the Local Lemma. Random Struct. Algorithms 2, 367–378 (1991)

    Article  MATH  Google Scholar 

  2. Alon N., Sudakov B., Zaks A.: Acyclic edge colorings of graphs. J. Graph Theory 37, 157–167 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alon N., Zaks A.: Algorithmic aspects of acyclic edge colorings. Algorithmica 32, 611–614 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  4. Basavaraju M., Chandran L.S.: Acyclic edge coloring of subcubic graphs. Discret. Math. 308, 6650–6653 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  5. Borodin O.V.: On acyclic colorings of planar graphs. Discret. Math. 25, 211–236 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  6. Burnstein, M.I.: Every 4-valent graph has an acyclic 5-coloring (in Russian), Soobšč Akad Nauk Gruzin SSR 93, 21–24 (1979) (Georgian and English summaries)

  7. Fiedorowicz A., Hałuszczak M., Narayanan N.: About acyclic edge colourings of planar graphs. Inform. Process. Lett. 108, 412–417 (2008)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Hou J., Liu G., Wang G.: Improved bounds for acyclic chromatic index of planar graphs. Discret. Appl. Math. 159, 876–881 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  10. Hou J., Wu J., Liu G., Liu B.: Acyclic edge colorings of planar graphs and series-parallel graphs. Sci. Chin. A 52, 605–616 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hou J., Wu J., Liu G., Liu B.: Acyclic edge chromatic number of outerplanar graphs. J. Graph Theory 64, 22–36 (2010)

    MathSciNet  MATH  Google Scholar 

  12. Kostochka A.K., Mel’nikov L.S.: Note to the paper of Grünbaum on acyclic colorings. Discret. Math. 14, 403–406 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  13. Molloy, M., Reed, B.: Further Algorithmic Aspects of the Local Lemma. In: Proceedings of the 30th annual ACM Symposium on theory of computing, 524–529 (1998)

  14. Muthu R., Narayanan N., Subramanian C.R.: Optimal acyclic edge colouring of grid like graphs. Lect. Notes Comp. Sci. 4112, 360–367 (2006)

    Article  MathSciNet  Google Scholar 

  15. Muthu R., Narayanan N., Subramanian C.R.: Acyclic edge colouring of outerplanar graphs. Lect. Notes Comp. Sci. 4508, 144–152 (2007)

    Article  Google Scholar 

  16. Skulrattanakulchai S.: Acyclic colorings of subcubic graphs. Inform. Process. Lett. 92, 161–167 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  17. Yu D., Hou J., Liu G., Liu B., Xu L.: Acyclic edge coloring of planar graphs with large girth. Theor. Comp. Sci. 410, 5196–5200 (2009)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Guizhen Liu.

Additional information

This work is supported by research grants NSFC (11001055, 10871119, 10631070, 10971121), NSFFP (2010J05004) and NSFSP (ZR2009AM009).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hou, J., Liu, G. & Wu, J. Acyclic Edge Coloring of Planar Graphs Without Small Cycles. Graphs and Combinatorics 28, 215–226 (2012). https://doi.org/10.1007/s00373-011-1043-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-011-1043-0

Keywords

Navigation