Unavoidable set of face types for planar maps

Mirko Horňák; Stanislav Jendrol

Discussiones Mathematicae Graph Theory (1996)

  • Volume: 16, Issue: 2, page 123-141
  • ISSN: 2083-5892

Abstract

top
The type of a face f of a planar map is a sequence of degrees of vertices of f as they are encountered when traversing the boundary of f. A set 𝒯 of face types is found such that in any normal planar map there is a face with type from 𝒯. The set 𝒯 has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.

How to cite

top

Mirko Horňák, and Stanislav Jendrol. "Unavoidable set of face types for planar maps." Discussiones Mathematicae Graph Theory 16.2 (1996): 123-141. <http://eudml.org/doc/270552>.

@article{MirkoHorňák1996,
abstract = {The type of a face f of a planar map is a sequence of degrees of vertices of f as they are encountered when traversing the boundary of f. A set 𝒯 of face types is found such that in any normal planar map there is a face with type from 𝒯. The set 𝒯 has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.},
author = {Mirko Horňák, Stanislav Jendrol},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {normal planar map; plane graph; type of a face; unavoidable set; cyclic chromatic number; planar map; face types},
language = {eng},
number = {2},
pages = {123-141},
title = {Unavoidable set of face types for planar maps},
url = {http://eudml.org/doc/270552},
volume = {16},
year = {1996},
}

TY - JOUR
AU - Mirko Horňák
AU - Stanislav Jendrol
TI - Unavoidable set of face types for planar maps
JO - Discussiones Mathematicae Graph Theory
PY - 1996
VL - 16
IS - 2
SP - 123
EP - 141
AB - The type of a face f of a planar map is a sequence of degrees of vertices of f as they are encountered when traversing the boundary of f. A set 𝒯 of face types is found such that in any normal planar map there is a face with type from 𝒯. The set 𝒯 has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.
LA - eng
KW - normal planar map; plane graph; type of a face; unavoidable set; cyclic chromatic number; planar map; face types
UR - http://eudml.org/doc/270552
ER -

References

top
  1. [1] O.V. Borodin, On the total coloring of planar graphs, J. reine angew. Math. 394 (1989) 180-185, doi: 10.1515/crll.1989.394.180. Zbl0653.05029
  2. [2] O.V. Borodin, Precise lower bound for the number of edges of minor weight in planar maps, Math. Slovaca 42 (1992) 129-142. Zbl0767.05039
  3. [3] O.V. Borodin, A structural theorem on planar maps and its application to coloring, Diskret. Mat. 4 (1992) 60-65. (Russian) Zbl0760.05034
  4. [4] O.V. Borodin, Structural properties of planar maps with the minimal degree 5, Math. Nachr. 158 (1992) 109-117, doi: 10.1002/mana.19921580108. Zbl0776.05035
  5. [5] O.V. Borodin, Joint extension of two theorems of Kotzig on 3-polytopes, Combinatorica 13 (1993) 121-125, doi: 10.1007/BF01202794. Zbl0777.05050
  6. [6] O.V. Borodin, The structure of edge neighbourhoods in plane graphs and the simultaneous coloring of vertices, edges and faces, Mat. Zametki 53 (1993) 35-47. (Russian) 
  7. [7] O.V. Borodin, Simultaneous coloring of edges and faces of plane graphs, Discrete Math. 128 (1994) 21-33, doi: 10.1016/0012-365X(94)90101-5. Zbl0807.05029
  8. [8] O.V. Borodin, Triangles with restricted degree sum of their boundary vertices in plane graphs, Discrete Math. 137 (1995) 45-51, doi: 10.1016/0012-365X(94)E0144-7. Zbl0814.05030
  9. [9] O.V. Borodin and D. P. Sanders, On light edges and triangles in planar graphs of minimum degree five, Math. Nachr. 170 (1994) 19-24, doi: 10.1002/mana.19941700103. Zbl0813.05020
  10. [10] B. Grünbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-408, doi: 10.1007/BF02764716. Zbl0265.05103
  11. [11] B. Grünbaum, New views on some old questions of combinatorial geometry, in.: Proc. Internat. Colloq. Combin. Theory (Rome, 1973) Accad. Naz. Lincei Rome (1976) 451-468. 
  12. [12] B. Grünbaum and G.C. Shephard, Analogues for tilings of Kotzig's theorem on minimal weights of edges, Ann. Discrete Math. 12 (1982) 129-140. Zbl0504.05026
  13. [13] J. Ivančo, The weight of a graph, Ann. Discrete Math. 51 (1992) 113-116, doi: 10.1016/S0167-5060(08)70614-9. Zbl0773.05066
  14. [14] S. Jendrol' and Z. Skupień, On the vertex/edge distance colourings of planar graphs, submitted. 
  15. [15] T.R. Jensen and B. Toft, Graph Coloring Problems (John Wiley&Sons, Inc. New York, 1995). 
  16. [16] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Casopis Sloven. Akad. Vied 5 (1955) 101-103. (Slovak) 
  17. [17] A. Kotzig, On the theory of Euler polyhedra, Mat.-Fyz. Casopis Sloven. Akad. Vied 13 (1963) 20-31. (Russian) 
  18. [18] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569-570. 
  19. [19] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 19-43. Zbl0024.28701
  20. [20] 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, New York (1969) 287-293. Zbl0195.25701
  21. [21] M.D. Plummer and B. Toft, Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987) 507-515, doi: 10.1002/jgt.3190110407. Zbl0655.05030
  22. [22] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. Zbl35.0511.01
  23. [23] J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281-296, doi: 10.1007/BF02804013. Zbl0524.05031

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.