Long induced paths in 3-connected planar graphs
Jorge Luis Arocha ; Pilar Valencia
Discussiones Mathematicae Graph Theory, Tome 20 (2000), p. 105-107 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

It is shown that every 3-connected planar graph with a large number of vertices has a long induced path.

Publié le : 2000-01-01
EUDML-ID : urn:eudml:doc:270666 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1110,
     author = {Jorge Luis Arocha and Pilar Valencia},
     title = {Long induced paths in 3-connected planar graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {20},
     year = {2000},
     pages = {105-107},
     zbl = {0960.05059},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1110}
}

Jorge Luis Arocha; Pilar Valencia. Long induced paths in 3-connected planar graphs. Discussiones Mathematicae Graph Theory, Tome 20 (2000) pp. 105-107. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1110/

[000] [1] P. Alles and S. Poljak, Long induced paths and cycles in Kneser graphs, Graphs Combin. 5 (1989) 303-306, doi: 10.1007/BF01788684. | Zbl 0688.05043

[001] [2] G. Bacsó and Z. Tuza, A Characterization of Graphs Without Long Induced Paths, J. Graph Theory 14 (1990) 455-464, doi: 10.1002/jgt.3190140409. | Zbl 0717.05044

[002] [3] F. Buckley and F. Harary, On longest induced path in graphs, Chinese Quart. J. Math. 3 (1988) 61-65.

[003] [4] J. Dong, Some results on graphs without long induced paths, J. Graph Theory 22 (1996) 23-28, doi: 10.1002/(SICI)1097-0118(199605)22:1<23::AID-JGT4>3.0.CO;2-N | Zbl 0849.05046

[004] [5] P. Erdős, M. Saks and V. Sós, Maximum Induced Trees in Graphs, J. Combin. Theory (B) 41 (1986) 61-79, doi: 10.1016/0095-8956(86)90028-6.

[005] [6] A. Frieze and B. Jackson, Large holes in sparse random graphs, Combinatorica 7 (1987) 265-274, doi: 10.1007/BF02579303. | Zbl 0662.05052

[006] [7] S. Suen, On large induced trees and long induced paths in sparse random graphs, J. Combin. Theory (B) 56 (1992) 250-262, doi: 10.1016/0095-8956(92)90021-O. | Zbl 0779.05052