ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2021): 1.028

5-year Journal Impact Factor (2021): 0.934

CiteScore (2021): 1.7

SNIP (2021): 1.157

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 22(2) (2002) 293-303


Tomás Madaras and Andrea Marcinová

Department of Geometry and Algebra
P.J. Safárik University
Jesenná 5, 041 54 Košice, Slovak Republic


We prove the structural result on normal plane maps, which applies to the vertex distance colouring of plane maps. The vertex distance-t chromatic number of a plane graph G with maximum degree Δ(G) ≤ D, D ≥ 12 is proved to be upper bounded by 6+[(2D+12)/(D−2)] ((D−1)(t−1)−1). This improves a recent bound 6+[(3D+3)/(D−2)]((D−1)t−1−1), D ≥ 8 by Jendrol' and Skupień, and the upper bound for distance-2 chromatic number.

Keywords: plane map, distance colouring.

2000 Mathematics Subject Classification: 05C10.


[1] P. Baldi, On a generalized family of colourings, Graphs and Combinatorics 6 (1990) 95-110, doi: 10.1007/BF01787722.
[2] O. Borodin, Joint generalization of theorems by Lebesgue and Kotzig, Diskret. Mat. 3 (1991) 24-27 (in Russian).
[3] O. Borodin, Joint colouring of vertices, edges and faces of plane graphs, Metody Diskret. Analiza 47 (1988) 27-37 (in Russian).
[4] M. Fellows, P. Hell and K. Seyffarth, Constructions of dense planar networks, manuscript, 1993.
[5] S. Jendrol' and Z. Skupień, On the vertex/edge distance colourings of planar graphs, Discrete Math. 236 (2001) 167-177.
[6] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV 5 (1955) 233-237 (in Slovak).
[7] F. Kramer and H. Kramer, Un problème de coloration des sommets d'un graphe, C.R. Acad. Sci. Paris Sér. A-B 268 (1969) A46-A48.
[8] F. Kramer and H. Kramer, On the generalized chromatic number, in: Combinatorics '84 (Bari, Italy) North-Holland Math. Stud. 123 (North-Holland, Amsterdam-New York, 1986) (and Annals Discrete Math. 30, 1986) 275-284.
[9] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. (9) 19 (1940) 27-43.
[10] Z. Skupień, Some maximum multigraphs and edge/vertex distance colourings, Discuss. Math. Graph Theory 15 (1995) 89-106, doi: 10.7151/dmgt.1010.
[11] J. van den Heuvel and S. McGuinness, Colouring the Square of a Planar Graph, preprint, 2001.
[12] G. Wegner, Graphs with given diameter and a coloring problem (Technical report, University of Dortmund, 1977).

Received 24 April 2001
Revised 23 March 2002