×

A unified approach to distance-two colouring of graphs on surfaces. (English) Zbl 1324.05052

Summary: In this paper we introduce the notion of \(\Sigma\)-colouring of a graph \(G\): For given subsets \(\Sigma(v)\) of neighbours of \(v\), for every \(v\in V(G)\), this is a proper colouring of the vertices of \(G\) such that, in addition, vertices that appear together in some \(\Sigma(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 F. Havet et al. [Electron. Notes Discrete Math. 29, 515–519 (2007; Zbl 1341.05073)], we reduce the problem to edge-colouring of multigraphs, and then use the result of J. Kahn [Random Struct. Algorithms 17, No. 2, 117–156 (2000; Zbl 0956.05038)] 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 \(\Delta\) embeddable in some fixed surface is at most \(\frac{3}{2}\Delta\) plus a constant.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] G. Agnarsson and M. M. Halldórsson: Coloring powers of planar graphs, SIAM J. Discrete Math.16 (2003), 651-662. · Zbl 1029.05047 · doi:10.1137/S0895480100367950
[2] J. A. Bondy and U. S. R. Murty: Graph Theory, Grad. Texts in Math. 244, Springer-Verlag, New York, 2008. · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5
[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. · Zbl 0565.05027
[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. 18, no. 4 (2001), 9-33. · Zbl 1012.05074
[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 Theory54 (2007), 58-72. · Zbl 1109.05042 · doi:10.1002/jgt.20193
[6] O. V. Borodin, D. P. Sanders and Y. Zhao: On cyclic colorings and their generalizations, Discrete Math.203 (1999), 23-40. · Zbl 0929.05027 · doi:10.1016/S0012-365X(99)00018-7
[7] N. Cohen and J. van den Heuvel: An exact bound on the clique number of the square of a planar graph, in preparation. · Zbl 0918.60035
[8] R. Diestel: Graph Theory, Grad. Texts in Math. 173, Springer-Verlag, Berlin, 2005. · Zbl 1074.05001
[9] J. Edmonds: Maximum matching and a polyhedron with 0;1-vertices, J. Res. Nat. Bur. Standards Sect. B69B (1965), 125-130. · Zbl 0141.21802 · doi:10.6028/jres.069B.013
[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. · Zbl 1341.05073
[11] P. Hell and K. Seyffarth: Largest planar graphs of diameter two and fixed maximum degree, Discrete Math.111 (1993), 313-322. · Zbl 0837.05074 · doi:10.1016/0012-365X(93)90166-Q
[12] T. J. Hetherington and D. R. Woodall: List-colouring the square of a K4-minorfree graph, Discrete Math.308 (2008), 4037-4043. · Zbl 1155.05024 · doi:10.1016/j.disc.2007.07.102
[13] J. van den Heuvel and S. McGuinness: Coloring the square of a planar graph, J. Graph Theory42 (2003), 110-124. · Zbl 1008.05065 · doi:10.1002/jgt.10077
[14] T. R. Jensen and B. Toft: Graph Coloring Problems, John-Wiley & Sons, New York, 1995. · Zbl 0855.05054
[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.
[16] J. Kahn: Asymptotics of the chromatic index for multigraphs, J. Combin. Theory Ser. B68 (1996), 233-254. · Zbl 0861.05026 · doi:10.1006/jctb.1996.0067
[17] J. Kahn: Asymptotics of the list-chromatic index for multigraphs, Random Structures Algorithms17 (2000), 117-156. · Zbl 0956.05038 · doi:10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9
[18] J. Kahn and P. M. Kayll: On the stochastic independence properties of hard-core distributions Combinatorica17 (1997), 369-391. · Zbl 0902.05055 · doi:10.1007/BF01215919
[19] A. V. Kostochka and D. R. Woodall: Choosability conjectures and multicircuits, Discrete Math.240 (2001), 123-143. · Zbl 0989.05041 · doi:10.1016/S0012-365X(00)00371-X
[20] Lee, C. W.; Lagarias, J. C (ed.); Todd, M. J (ed.), Some recent results on convex polytopes, No. 114, 3-19 (1990) · doi:10.1090/conm/114/1097862
[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. · Zbl 1027.05042 · doi:10.1016/S0012-365X(03)00059-1
[22] W. Mader: Homomorphiesätze für Graphen, Math. Ann.178 (1968), 154-168. · Zbl 0165.57401 · doi:10.1007/BF01350657
[23] B. Mohar and C. Thomassen: Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001. · Zbl 0979.05002
[24] M. Molloy and B. Reed: Graph Colouring and the Probabilistic Method, Algorithms Combin. 23, Springer-Verlag, Berlin, 2002. · Zbl 0987.05002 · doi:10.1007/978-3-642-04016-0
[25] M. Molloy and M. R. Salavatipour: A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B94 (2005), 189-213. · Zbl 1071.05036 · doi:10.1016/j.jctb.2004.12.005
[26] Ore, O.; Plummer, M. D., Cyclic coloration of plane graphs, 287-293 (1969), San Diego · Zbl 0195.25701
[27] Rabinovich, Y.; Sinclair, A.; Wigderson, A., Quadratic dynamical systems, 304-313 (1992) · Zbl 0918.60035
[28] N. Robertson and P. Seymour: Graph minors XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B81 (2003), 43-76. · Zbl 1023.05040 · doi:10.1016/S0095-8956(03)00042-X
[29] D. P. Sanders and Y. Zhao: A new bound on the cyclic chromatic number, J. Combin. Theory Ser. B83 (2001), 102-111. · Zbl 1027.05044 · doi:10.1006/jctb.2001.2046
[30] Schrijver, A., Combinatorial Optimization; Polyhedra and Efficiency (2003), Berlin · Zbl 1041.90001
[31] C. E. Shannon: A theorem on colouring lines of a network, J. Math. Physics28 (1949), 148-151. · Zbl 0032.43203
[32] V. G. Vizing: On an estimate of the chromatic class of a p-graph (in Russian), Metody Diskret. Analiz.3 (1964), 25-30.
[33] G. Wegner: Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, 1977.
[34] S. A. Wong: Colouring graphs with respect to distance, M.Sc. Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1996.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.