Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Entire Coloring of Graphs Embedded in a Surface of Nonnegative Characteristic

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

Abstract

LetG be a graph embedded in a surface of nonnegative characteristic with maximum degree\(\varDelta \). The entire chromatic number\(\chi _\mathrm{vef}\) ofG is the least number of colors such that any two adjacent or incident elements in\(V(G)\cup E(G) \cup F(G)\) have different colors. In this paper, we prove that\(\chi _\mathrm{vef}(G)\le \varDelta +4\) if\(\varDelta \ge 6\), and\(\chi _\mathrm{vef}(G)\le \varDelta +5\) if\(\varDelta \le 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
¥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.

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Albertson, M.O., Mohar, B.: Coloring vertices and faces of locally planar graphs. Graphs Comb.22, 289–295 (2006)

    Article MathSciNet  Google Scholar 

  2. Appel, K., Haken, W.: Every planar graph map is four colourable. Bull. Am. Math. Soc.82, 711–712 (1976)

    Article  Google Scholar 

  3. Böhme, T., Mohar, B., Stiebitz, M.: Dirac’s map-color theorem for choosability. J. Graph Theory32, 327–339 (1999)

    Article MathSciNet  Google Scholar 

  4. Borodin, O.V.: A new proof of the 6 colour theorem. J. Graph Theory19, 507–521 (1995)

    Article MathSciNet  Google Scholar 

  5. Borodin, O.V.: Structural theorem on plane graphs with application to the entire coloring number. J. Graph Theory23, 233–239 (1996)

    Article MathSciNet  Google Scholar 

  6. Cai, L., Wang, W., Zhu, X.: Choosability of toroidal graphs without short cycles. J. Graph Theory65, 1–15 (2010)

    MathSciNet MATH  Google Scholar 

  7. Harris, A.J.: Problems and conjectures in extremal graph theory. Graphs Comb.2, 189–190 (1985)

    Google Scholar 

  8. Heawood, P.J.: Map-color theorems. Q. J. Math.24, 332–338 (1890)

    MATH  Google Scholar 

  9. Hu, X., Wang, P., Wang, Y., Wang, W.: The entire chromatic number of graphs embedded on the torus with large maximum degree. Theor. Comput. Sci.689, 108–116 (2017)

    Article MathSciNet  Google Scholar 

  10. Juvan, M., Mohar, B., Škrekovski, R.: Graphs of degree 4 are 5-edge-choosable. J. Graph Theory32, 250–264 (1999)

    Article MathSciNet  Google Scholar 

  11. Král, D., Thomas, R.: Coloring even-faced graphs in the torus and the Klein bottle. Combinatorica28, 325–341 (2008)

    Article MathSciNet  Google Scholar 

  12. Kronk, H.V., Mitchem, J.: A seven-color theorem on the sphere. Discret. Math.5, 253–260 (1973)

    Article MathSciNet  Google Scholar 

  13. Luo, X.: The 4-choosability of toroidal graphs without intersecting triangles. Inf. Process. Lett.102, 85–91 (2007)

    Article MathSciNet  Google Scholar 

  14. Mel’nikov, L.S.: Problem 9. In: Recent Advances in Graph Theory, Proceedings of the International Symposium, Prague, 1974, p. 543. Academia Praha, Prague (1975)

  15. Ringel, G., Youngs, J.W.T.: Solution of the Heawood map-coloring problem. Proc. Natl. Acad. Sci. USA60, 438–445 (1968)

    Article MathSciNet  Google Scholar 

  16. Ringel, G.: A nine color theorem for the torus and the Klein bottle. In: The Theory and Applications of Graphs (Kalamazoo, Michigan, 1980), pp. 507–515. Wiley, New York (1981)

  17. Schumacher, H.: About the chromatic number of 1-embeddable graphs. In: Graph Theory in Memory of G.A. Dirac (Sandbjerg, 1985). Annals of Discrete Mathematics, vol. 41, pp. 397–400. North Holland, Amsterdam (1989)

    Chapter  Google Scholar 

  18. Sanders, D.P., Maharry, J.: On simultaneous colorings of embedded graphs. Discret. Math.224, 207–214 (2000)

    Article MathSciNet  Google Scholar 

  19. Sanders, D.P., Zhao, Y.: On simultaneous edge-face colourings of plane graphs. Combinatorica17, 441–445 (1997)

    MathSciNet MATH  Google Scholar 

  20. Sanders, D.P., Zhao, Y.: On the entire coloring conjecture. Can. Math. Bull.43, 108–114 (2000)

    Article MathSciNet  Google Scholar 

  21. Wang, W.: The edge-face coloring of graphs embedded in a surface of characteristic zero. Discret. Math.309, 3523–3533 (2009)

    Article MathSciNet  Google Scholar 

  22. Wang, W., Lih, K.-W.: A new proof of Mel’nikov’s conjecture on the edge-face colouring of plane graphs. Discret. Math.253, 87–95 (2002)

    Article  Google Scholar 

  23. Wang, W., Lih, K.-W.: The edge-face choosability of plane graphs. Eur. J. Comb.25, 935–948 (2004)

    Article MathSciNet  Google Scholar 

  24. Wang, W., Lih, K.-W.: Coupled choosability of plane graphs. J. Graph Theory58, 27–44 (2008)

    Article MathSciNet  Google Scholar 

  25. Wang, W., Zhu, X.: Entire colouring of plane graphs. J. Comb. Theory Ser. B101, 490–501 (2011)

    Article MathSciNet  Google Scholar 

  26. Wang, Y., Hu, X., Wang, W.: Plane graphs with\(\varDelta \ge 9\) are entirely\((\varDelta +2)\)-colorable. SIAM J. Discret. Math.28, 1892–1905 (2014)

    Article  Google Scholar 

  27. Waller, A.O.: Simultaneously colouring the edges and faces of plane graphs. J. Comb. Theory Ser. B69, 219–221 (1997)

    Article MathSciNet  Google Scholar 

  28. Yap, H.P.: Total Colourings of Graphs. Lecture Notes in Mathematics, vol. 16. Springer, Berlin (1996)

    Book  Google Scholar 

Download references

Acknowledgements

The authors are most grateful to the referees whose comments led to an improved version of our paper. The first author’s research is supported by NSFC (nos. 11801512, 11701541 and 11571315). The second author’s research is supported by NSFC (no. 11771402). The third author’s research is supported by NSFC (no. 11671053).

Author information

Authors and Affiliations

  1. School of Science, Zhejiang University of Science and Technology, Hangzhou, 310023, China

    Xiaoxue Hu

  2. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China

    Weifan Wang

  3. School of Management, Beijing University of Chinese Medicine, Beijing, 100029, China

    Yiqiao Wang

  4. Department of Mathematics, Statistics and Computer Science, St. Francis Xavier University, Antigonish, Nova Scotia, Canada

    Ping Wang

Authors
  1. Xiaoxue Hu

    You can also search for this author inPubMed Google Scholar

  2. Weifan Wang

    You can also search for this author inPubMed Google Scholar

  3. Yiqiao Wang

    You can also search for this author inPubMed Google Scholar

  4. Ping Wang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toWeifan Wang.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hu, X., Wang, W., Wang, Y.et al. Entire Coloring of Graphs Embedded in a Surface of Nonnegative Characteristic.Graphs and Combinatorics34, 1489–1506 (2018). https://doi.org/10.1007/s00373-018-1971-z

Download citation

Keywords

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.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp