On the structural result on normal plane maps

Tomás Madaras; Andrea Marcinová

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 2, page 293-303
  • ISSN: 2083-5892

Abstract

top
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 + [ ( 2 D + 12 ) / ( D - 2 ) ] ( ( D - 1 ) ( t - 1 ) - 1 ) . This improves a recent bound 6 + [ ( 3 D + 3 ) / ( D - 2 ) ] ( ( D - 1 ) t - 1 - 1 ) , D ≥ 8 by Jendrol’ and Skupień, and the upper bound for distance-2 chromatic number.

How to cite

top

Tomás Madaras, and Andrea Marcinová. "On the structural result on normal plane maps." Discussiones Mathematicae Graph Theory 22.2 (2002): 293-303. <http://eudml.org/doc/270155>.

@article{TomásMadaras2002,
abstract = {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.},
author = {Tomás Madaras, Andrea Marcinová},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {plane map; distance colouring},
language = {eng},
number = {2},
pages = {293-303},
title = {On the structural result on normal plane maps},
url = {http://eudml.org/doc/270155},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Tomás Madaras
AU - Andrea Marcinová
TI - On the structural result on normal plane maps
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 2
SP - 293
EP - 303
AB - 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.
LA - eng
KW - plane map; distance colouring
UR - http://eudml.org/doc/270155
ER -

References

top
  1. [1] P. Baldi, On a generalized family of colourings, Graphs and Combinatorics 6 (1990) 95-110, doi: 10.1007/BF01787722. Zbl0716.05018
  2. [2] O. Borodin, Joint generalization of theorems by Lebesgue and Kotzig, Diskret. Mat. 3 (1991) 24-27 (in Russian). Zbl0742.05034
  3. [3] O. Borodin, Joint colouring of vertices, edges and faces of plane graphs, Metody Diskret. Analiza 47 (1988) 27-37 (in Russian). Zbl0707.05023
  4. [4] M. Fellows, P. Hell and K. Seyffarth, Constructions of dense planar networks, manuscript, 1993. 
  5. [5] S. Jendrol' and Z. Skupień, On the vertex/edge distance colourings of planar graphs, Discrete Math. 236 (2001) 167-177. 
  6. [6] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV 5 (1955) 233-237 (in Slovak). 
  7. [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. Zbl0165.57302
  8. [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. [9] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. (9) 19 (1940) 27-43. Zbl0024.28701
  10. [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. [11] J. van den Heuvel and S. McGuinness, Colouring the Square of a Planar Graph, preprint, 2001. Zbl1008.05065
  12. [12] G. Wegner, Graphs with given diameter and a coloring problem (Technical report, University of Dortmund, 1977). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.