Skip to main content
SpringerLink
Log in

A unified approach to distance-two colouring of graphs on surfaces

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

In this paper we introduce the notion of Σ-colouring of a graph G: For given subsets Σ(v) of neighbours of v, for every v∈V (G), this is a proper colouring of the vertices of G such that, in addition, vertices that appear together in some Σ(v) receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result for graphs embeddable in a fixed surface, which implies asymptotic versions of Wegner’s and Borodin’s Conjecture on the planar version of these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs, and then use Kahn’s result that the list chromatic index is close to the fractional chromatic index.

Our results are based on a strong structural lemma for graphs embeddable in a fixed surface, which also implies that the size of a clique in the square of a graph of maximum degree Δ embeddable in some fixed surface is at most \( \frac{3} {2}\Delta \) plus a constant.

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

Access this article

Log in via an institution

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. G. Agnarsson and M. M. Halldórsson: Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003), 651–662.

    Article  MATH  MathSciNet  Google Scholar 

  2. J. A. Bondy and U. S. R. Murty: Graph Theory, Grad. Texts in Math. 244, Springer-Verlag, New York, 2008.

    Book  MATH  Google Scholar 

  3. O. V. Borodin: Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs (in Russian), Metody Diskret. Analyz. 41 (1984), 12–26.

    MATH  MathSciNet  Google Scholar 

  4. O. V. Borodin, H. J. Broersma, A. Glebov and J. van den Heuvel: Minimal degrees and chromatic numbers of squares of planar graphs (in Russian), Diskretn. Anal. Issled. Oper. Ser. 1 8, no. 4 (2001), 9–33.

    MATH  MathSciNet  Google Scholar 

  5. O. V. Borodin, H. J. Broersma, A. Glebov and J. van den Heuvel: A new upper bound on the cyclic chromatic number, J. Graph Theory 54 (2007), 58–72.

    Article  MATH  MathSciNet  Google Scholar 

  6. O. V. Borodin, D. P. Sanders and Y. Zhao: On cyclic colorings and their generalizations, Discrete Math. 203 (1999), 23–40.

    Article  MATH  MathSciNet  Google Scholar 

  7. N. Cohen and J. van den Heuvel: An exact bound on the clique number of the square of a planar graph, in preparation.

  8. R. Diestel: Graph Theory, Grad. Texts in Math. 173, Springer-Verlag, Berlin, 2005.

    MATH  Google Scholar 

  9. J. Edmonds: Maximum matching and a polyhedron with 0;1-vertices, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125–130.

    Article  MathSciNet  Google Scholar 

  10. F. Havet, J. van den Heuvel, C. McDiarmid and B. Reed: List colouring squares of planar graphs, Preprint (2008), arxiv.org/abs/0807.3233.

    Google Scholar 

  11. P. Hell and K. Seyffarth: Largest planar graphs of diameter two and fixed maximum degree, Discrete Math. 111 (1993), 313–322.

    Article  MATH  MathSciNet  Google Scholar 

  12. T. J. Hetherington and D. R. Woodall: List-colouring the square of a K4-minorfree graph, Discrete Math. 308 (2008), 4037–4043.

    Article  MATH  MathSciNet  Google Scholar 

  13. J. van den Heuvel and S. McGuinness: Coloring the square of a planar graph, J. Graph Theory 42 (2003), 110–124.

    Article  MATH  MathSciNet  Google Scholar 

  14. T. R. Jensen and B. Toft: Graph Coloring Problems, John-Wiley & Sons, New York, 1995.

    MATH  Google Scholar 

  15. T. K. Jonas: Graph coloring analogues with a condition at distance two: L(2; 1)-labelings and list λ-labelings, Ph.D. Thesis, University of South Carolina, 1993.

    Google Scholar 

  16. J. Kahn: Asymptotics of the chromatic index for multigraphs, J. Combin. Theory Ser. B 68 (1996), 233–254.

    Article  MATH  MathSciNet  Google Scholar 

  17. J. Kahn: Asymptotics of the list-chromatic index for multigraphs, Random Structures Algorithms 17 (2000), 117–156.

    Article  MATH  MathSciNet  Google Scholar 

  18. J. Kahn and P. M. Kayll: On the stochastic independence properties of hard-core distributions Combinatorica 17 (1997), 369–391.

    Article  MATH  MathSciNet  Google Scholar 

  19. A. V. Kostochka and D. R. Woodall: Choosability conjectures and multicircuits, Discrete Math. 240 (2001), 123–143.

    Article  MATH  MathSciNet  Google Scholar 

  20. C. W. Lee: Some recent results on convex polytopes, in: J. C. Lagarias and M. J. Todd, eds., Mathematical Developments Arising from Linear Programming, Contemp. Math. 114 (1990), 3–19.

    Chapter  Google Scholar 

  21. K.-W. Lih, W. F. Wang and X. Zhu: Coloring the square of a K4-minor free graph, Discrete Math. 269 (2003), 303–309.

    Article  MATH  MathSciNet  Google Scholar 

  22. W. Mader: Homomorphiesätze für Graphen, Math. Ann. 178 (1968), 154–168.

    Article  MATH  MathSciNet  Google Scholar 

  23. B. Mohar and C. Thomassen: Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001.

    MATH  Google Scholar 

  24. M. Molloy and B. Reed: Graph Colouring and the Probabilistic Method, Algorithms Combin. 23, Springer-Verlag, Berlin, 2002.

    Book  MATH  Google Scholar 

  25. M. Molloy and M. R. Salavatipour: A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B 94 (2005), 189–213.

    Article  MATH  MathSciNet  Google Scholar 

  26. O. Ore and M. D. Plummer: Cyclic coloration of plane graphs, in: Recent Progress in Combinatorics; Proceedings of the Third Waterloo Conference on Combinatorics, Academic Press, San Diego (1969) 287–293.

    Google Scholar 

  27. Y. Rabinovich, A. Sinclair and A. Wigderson: Quadratic dynamical systems, in: Proceedings of the 33rd Annual Conference on Foundations of Computer Science (FOCS), (1992), 304–313.

    Google Scholar 

  28. N. Robertson and P. Seymour: Graph minors XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B 81 (2003), 43–76.

    Article  MathSciNet  Google Scholar 

  29. D. P. Sanders and Y. Zhao: A new bound on the cyclic chromatic number, J. Combin. Theory Ser. B 83 (2001), 102–111.

    Article  MATH  MathSciNet  Google Scholar 

  30. A. Schrijver: Combinatorial Optimization; Polyhedra and Efficiency, Algorithms Combin. 24, Springer-Verlag, Berlin, 2003.

    Google Scholar 

  31. C. E. Shannon: A theorem on colouring lines of a network, J. Math. Physics 28 (1949), 148–151.

    MATH  MathSciNet  Google Scholar 

  32. V. G. Vizing: On an estimate of the chromatic class of a p-graph (in Russian), Metody Diskret. Analiz. 3 (1964), 25–30.

    MathSciNet  Google Scholar 

  33. G. Wegner: Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, 1977.

    Google Scholar 

  34. S. A. Wong: Colouring graphs with respect to distance, M.Sc. Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1996.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CNRS — DMA, École Normale Supérieure, Paris, France

    Omid Amini

  2. CNRS — Laboratoire G-SCOP, Grenoble, France

    Louis Esperet

  3. Department of Mathematics, London School of Economics, London, UK

    Jan Van Den Heuvel

Authors
  1. Omid Amini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Louis Esperet
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jan Van Den Heuvel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Omid Amini.

Additional information

This paper benefited greatly from helpful comments of anonymous referees. The authors would like to thank the referees for careful reading of the paper and for their constructive suggestions.

The research for this paper was started during a visit of LE and JvdH to the Mascotte research group at INRIA Sophia-Antipolis, where OA was a PhD student (joint with École Polytechnique). The authors like to thank the members of Mascotte for their hospitality.

JvdH’s visit to INRIA Sophia-Antipolis was partly supported by a grant from the Alliance Programme of the British Council.

Part of this research has been conducted while OA was visiting McGill University in Montreal. He warmly thanks Bruce Reed for providing the possibility for such a visit.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Amini, O., Esperet, L. & Van Den Heuvel, J. A unified approach to distance-two colouring of graphs on surfaces. Combinatorica 33, 253–296 (2013). https://doi.org/10.1007/s00493-013-2573-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-013-2573-2

Mathematics Subject Classification (2010)

Search

Navigation