Geodesic
Paths of low weight in planar graphs
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 1, pp. 121-135.

Voir la notice de l'article provenant de la source Library of Science

The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are:
Keywords: planar graphs, polytopal graphs, paths, weight of an edge, weight of a path 
@article{DMGT_2008_28_1_a8,
     author = {Fabrici, Igor and Harant, Jochen and Jendrol', Stanislav},
     title = {Paths of low weight in planar graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {121--135},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_1_a8/}
}
TY  - JOUR
AU  - Fabrici, Igor
AU  - Harant, Jochen
AU  - Jendrol', Stanislav
TI  - Paths of low weight in planar graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 121
EP  - 135
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_1_a8/
LA  - en
ID  - DMGT_2008_28_1_a8
ER  - 
%0 Journal Article
%A Fabrici, Igor
%A Harant, Jochen
%A Jendrol', Stanislav
%T Paths of low weight in planar graphs
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 121-135
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_1_a8/
%G en
%F DMGT_2008_28_1_a8
Fabrici, Igor; Harant, Jochen; Jendrol', Stanislav. Paths of low weight in planar graphs. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 1, pp. 121-135. http://geodesic.mathdoc.fr/item/DMGT_2008_28_1_a8/

[1] K. Ando, S. Iwasaki and A. Kaneko, Every 3-connected planar graph has a connected subgraph with small degree sum, Annual Meeting of Mathematical Society of Japan, 1993, Japanese.

[2] G. Chen and X. Yu, Long cycles in 3-connected graphs, J. Combin. Theory (B) 86 (2002) 80-99, doi: 10.1006/jctb.2002.2113.

[3] E. Etourneau, Existence and connectivity of planar having 12 vertices of degree 5 and, n-12 vertices of degree 6, Colloq. Math. Soc. János Bolyai 10 (1975) 645-655.

[4] H. Enomoto and K. Ota, Connected subgraphs with small degree sum in 3-connected planar graphs, J. Graph Theory 30 (1999) 191-203, doi: 10.1002/(SICI)1097-0118(199903)30:3191::AID-JGT4>3.0.CO;2-X

[5] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245-250.

[6] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar graphs. Discrete Math. 191 (1998) 83-90, doi: 10.1016/S0012-365X(98)00095-8.

[7] P. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527.

[8] B. Grünbaum, New views on some old questions of combinatorial geometry, Int. Teorie Combinatorie, Rome 1 (1976) 451-468.

[9] J. Harant and S. Jendrol', On the existence of specific stars in planar graph, Graphs and Combinatorics 23 (2007) 529-543, doi: 10.1007/s00373-007-0747-7.

[10] J. Harant, S. Jendrol' and M. Tkáč, On 3-connected plane graphs without triangular faces, J. Combin. Theory (B) 77 (1999) 150-161, doi: 10.1006/jctb.1999.1918.

[11] J. van den Heuvel and S. McGuinness, Coloring the square of a planar graph, J. Graph Theory 42 (2003) 110-124, doi: 10.1002/jgt.10077.

[12] S. Jendrol', Paths with restricted degrees of their vertices in planar graphs, Czechoslovak Math. J. 49 (1999) 481-490, doi: 10.1023/A:1022411100562.

[13] S. Jendrol', T. Madaras, R. Soták and Z. Tuza, On light cycles in plane triangulations, Discrete Math. 197/198 (1999) 453-467, doi: 10.1016/S0012-365X(99)90099-7.

[14] S. Jendrol' and H.-J. Voss, Light subgraphs of graphs embedded in the plane and in the projective plane - a survey, P.J. Šafárik University Košice, IM Preprint series (A) No. 1 (2004).

[15] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV (Math. Slovaca) 5 (1955) 101-113.

[16] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 565-570.

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

[18] T. Madaras, Note on weights of paths in polyhedral graphs, Discrete Math. 203 (1999) 267-269, doi: 10.1016/S0012-365X(99)00052-7.

[19] B. Mohar, Light paths in 4-connected graphs in the plane and other surfaces, J. Graph Theory 34 (2000) 170-179, doi: 10.1002/1097-0118(200006)34:2170::AID-JGT6>3.0.CO;2-P

[20] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99-116, doi: 10.1090/S0002-9947-1956-0081471-8.

[21] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968.