# 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

## Access Full Article

top## Abstract

top## How to cite

topMirko 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] 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] 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] O.V. Borodin, A structural theorem on planar maps and its application to coloring, Diskret. Mat. 4 (1992) 60-65. (Russian) Zbl0760.05034
- [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] 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] 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] 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] 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] 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] B. Grünbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-408, doi: 10.1007/BF02764716. Zbl0265.05103
- [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] 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] 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] S. Jendrol' and Z. Skupień, On the vertex/edge distance colourings of planar graphs, submitted.
- [15] T.R. Jensen and B. Toft, Graph Coloring Problems (John Wiley&Sons, Inc. New York, 1995).
- [16] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Casopis Sloven. Akad. Vied 5 (1955) 101-103. (Slovak)
- [17] A. Kotzig, On the theory of Euler polyhedra, Mat.-Fyz. Casopis Sloven. Akad. Vied 13 (1963) 20-31. (Russian)
- [18] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569-570.
- [19] H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 19-43. Zbl0024.28701
- [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] 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] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. Zbl35.0511.01
- [23] J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281-296, doi: 10.1007/BF02804013. Zbl0524.05031

## Citations in EuDML Documents

top## NotesEmbed ?

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