On the structural result on normal plane maps
Tomás Madaras ; Andrea Marcinová
Discussiones Mathematicae Graph Theory, Tome 22 (2002), p. 293-303 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2002-01-01
EUDML-ID : urn:eudml:doc:270155 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1176,
     author = {Tom\'as Madaras and Andrea Marcinov\'a},
     title = {On the structural result on normal plane maps},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {22},
     year = {2002},
     pages = {293-303},
     zbl = {1027.05028},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1176}
}

Tomás Madaras; Andrea Marcinová. On the structural result on normal plane maps. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 293-303. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1176/

[000] [1] P. Baldi, On a generalized family of colourings, Graphs and Combinatorics 6 (1990) 95-110, doi: 10.1007/BF01787722. | Zbl 0716.05018

[001] [2] O. Borodin, Joint generalization of theorems by Lebesgue and Kotzig, Diskret. Mat. 3 (1991) 24-27 (in Russian). | Zbl 0742.05034

[002] [3] O. Borodin, Joint colouring of vertices, edges and faces of plane graphs, Metody Diskret. Analiza 47 (1988) 27-37 (in Russian). | Zbl 0707.05023

[003] [4] M. Fellows, P. Hell and K. Seyffarth, Constructions of dense planar networks, manuscript, 1993.

[004] [5] S. Jendrol' and Z. Skupień, On the vertex/edge distance colourings of planar graphs, Discrete Math. 236 (2001) 167-177.

[005] [6] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV 5 (1955) 233-237 (in Slovak).

[006] [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. | Zbl 0165.57302

[007] [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.

[008] [9] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. (9) 19 (1940) 27-43. | Zbl 0024.28701

[009] [10] Z. Skupień, Some maximum multigraphs and edge/vertex distance colourings, Discuss. Math. Graph Theory 15 (1995) 89-106, doi: 10.7151/dmgt.1010.

[010] [11] J. van den Heuvel and S. McGuinness, Colouring the Square of a Planar Graph, preprint, 2001. | Zbl 1008.05065

[011] [12] G. Wegner, Graphs with given diameter and a coloring problem (Technical report, University of Dortmund, 1977).