Long induced paths in 3-connected planar graphs
Jorge Luis Arocha; Pilar Valencia
Discussiones Mathematicae Graph Theory (2000)
- Volume: 20, Issue: 1, page 105-107
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topJorge Luis Arocha, and Pilar Valencia. "Long induced paths in 3-connected planar graphs." Discussiones Mathematicae Graph Theory 20.1 (2000): 105-107. <http://eudml.org/doc/270666>.
@article{JorgeLuisArocha2000,
abstract = {It is shown that every 3-connected planar graph with a large number of vertices has a long induced path.},
author = {Jorge Luis Arocha, Pilar Valencia},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {induced paths; 3-connected planar graphs; long path; embedding},
language = {eng},
number = {1},
pages = {105-107},
title = {Long induced paths in 3-connected planar graphs},
url = {http://eudml.org/doc/270666},
volume = {20},
year = {2000},
}
TY - JOUR
AU - Jorge Luis Arocha
AU - Pilar Valencia
TI - Long induced paths in 3-connected planar graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 1
SP - 105
EP - 107
AB - It is shown that every 3-connected planar graph with a large number of vertices has a long induced path.
LA - eng
KW - induced paths; 3-connected planar graphs; long path; embedding
UR - http://eudml.org/doc/270666
ER -
References
top- [1] P. Alles and S. Poljak, Long induced paths and cycles in Kneser graphs, Graphs Combin. 5 (1989) 303-306, doi: 10.1007/BF01788684. Zbl0688.05043
- [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. Zbl0717.05044
- [3] F. Buckley and F. Harary, On longest induced path in graphs, Chinese Quart. J. Math. 3 (1988) 61-65.
- [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 Zbl0849.05046
- [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.
- [6] A. Frieze and B. Jackson, Large holes in sparse random graphs, Combinatorica 7 (1987) 265-274, doi: 10.1007/BF02579303. Zbl0662.05052
- [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. Zbl0779.05052
NotesEmbed ?
topYou 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.