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

Homomorphism Bounds for Oriented Planar Graphs of Given Minimum Girth

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

Abstract

We find necessary conditions for a digraph H to admit a homomorphism from every oriented planar graph of girth at least n, and use these to prove the existence of a planar graph of girth 6 and oriented chromatic number at least 7. We identify a \({\overleftrightarrow{K_4}}\) -free digraph of order 7 which admits a homomorphism from every oriented planar graph (here \({\overleftrightarrow{K_n}}\) means a digraph with n vertices and arcs in both directions between every distinct pair), and a \({\overleftrightarrow{K_3}}\) -free digraph of order 4 which admits a homomorphism from every oriented planar graph of girth at least 5.

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. Marshall T.H.: Homomorphism bounds for oriented planar graphs. J. Graph Theory 55, 175–190 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Raspaud A., Sopena E.: Good and semi-strong colorings of oriented planar graphs. Inform. Proc. Lett. 51, 171–174 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  3. Marshall, T.H.: On oriented graphs with certain extension properties. Ars Combinatoria (2012, in press)

  4. Borodin, Ivanova, A.O.: An oriented 7-coloring of planar graphs with girth at least 7. Sib. Electron. Math. Rep. 2, 222–229 (2005)

  5. Borodin O.V., Ivanova A.O., Kostochka A.V.: Oriented 5-coloring of vertices in sparse graphs. (Russian) Diskretn. Anal. Issled. Oper. Ser. 1 13(1), 16–32 (2006)

    MathSciNet  MATH  Google Scholar 

  6. Borodin O.V., Kostochka A.V., Nešetřil J., Raspaud A., Sopena E.: On the maximum average degree and the oriented chromatic number of a graph. Discret. Math. 206, 77–90 (1999)

    Article  MATH  Google Scholar 

  7. Nešetřil, J., Raspaud, A., Sopena, E.: Colorings and girth of oriented planar graphs. Discret. Math. 165–166, 519–530 (1997)

    Google Scholar 

  8. Ochem P.: Oriented colorings of triangle-free planar graphs. Inform. Process. Lett. 92, 71–76 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  9. Ochem P., Pinlou A.: Oriented colorings of partial 2-trees. Inform. Process. Lett. 108(2), 82–86 (2008)

    Article  MathSciNet  Google Scholar 

  10. Ochem P., Pinlou A.: Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs. Elect. Notes Discret. Math. 37, 123–128 (2011)

    Article  MathSciNet  Google Scholar 

  11. Pinlou A.: An oriented coloring of planar graphs with girth at least five. Discret. Math. 309, 2108–2118 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. Thomassen C.: Every planar graph is 5-choosable. J. Combin. Theory Ser. B 62, 180–181 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  13. Thomassen C.: A short list color proof of Grötzsch’s theorem. J. Combin. Theory Ser. B 88(1), 189–192 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  14. Sopena E.: There exist oriented planar graphs with oriented chromatic number at least sixteen. Inform. Proc. Lett. 81, 309–312 (2002)

    Article  MathSciNet  Google Scholar 

  15. Pinlou A., Sopena E.: Oriented vertex and arc colorings of outerplanar graphs. Inform. Proc. Lett. 100, 97–104 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  16. Marshall, T.H.: Homomorphism Bounds for Oriented Planar Graphs of Given Minimum Girth. KAM Dimatia, Czech Republic (2011, preprint)

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, American University of Sharjah, PO Box 26666, Sharjah, United Arab Emirates

    T. H. Marshall

Authors
  1. T. H. Marshall
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to T. H. Marshall.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Marshall, T.H. Homomorphism Bounds for Oriented Planar Graphs of Given Minimum Girth. Graphs and Combinatorics 29, 1489–1499 (2013). https://doi.org/10.1007/s00373-012-1202-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-012-1202-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation