Disjoint paths, planarizing cycles, and spanning walks

Yu, Xingxing

doi:10.1090/S0002-9947-97-01830-8

Disjoint paths, planarizing cycles, and
spanning walks

Author: Xingxing Yu
Journal: Trans. Amer. Math. Soc. 349 (1997), 1333-1358
MSC (1991): Primary 05C38, 05C10, 57M15
DOI: https://doi.org/10.1090/S0002-9947-97-01830-8
MathSciNet review: 1401533
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the existence of certain disjoint paths in planar graphs and generalize a theorem of Thomassen on planarizing cycles in surfaces. Results are used to prove that every 5-connected triangulation of a surface with sufficiently large representativity is hamiltonian, thus verifying a conjecture of Thomassen. We also obtain results about spanning walks in graphs embedded in a surface with large representativity.

1. J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988
2. Richard Brunet, Mark N. Ellingham, Zhicheng Gao, Alice Metzlar, and R. Bruce Richter, Spanning planar subgraphs of graphs in the torus and Klein bottle, J. Combin. Theory Ser. B 65 (1995), no. 1, 7–22. MR 1347338, https://doi.org/10.1006/jctb.1995.1041
3. Richard A. Duke, On the genus and connectivity of Hamiltonian graphs, Discrete Math. 2 (1972), no. 3, 199–206. MR 314670, https://doi.org/10.1016/0012-365X(72)90003-9
4. M. N. Ellingham and Zhicheng Gao, Spanning trees in locally planar triangulations, J. Combin. Theory Ser. B 61 (1994), no. 2, 178–198. MR 1280606, https://doi.org/10.1006/jctb.1994.1043
5. Zhicheng Gao and R. Bruce Richter, 2-walks in circuit graphs, J. Combin. Theory Ser. B 62 (1994), no. 2, 259–267. MR 1305052, https://doi.org/10.1006/jctb.1994.1068
6. Branko Grünbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc. 76 (1970), 1131–1201. MR 266050, https://doi.org/10.1090/S0002-9904-1970-12601-5
7. Allan Gewirtz and Louis V. Quintas (eds.), Second International Conference on Combinatorial Mathematics, Annals of the New York Academy of Sciences, vol. 319, New York Academy of Sciences, New York, 1979. Held in New York, April 4–7, 1978. MR 555999
8. C. St. J. A. Nash-Williams, Unexplored and semi-explored territories in graph theory, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971) Academic Press, New York, 1973, pp. 149–186. MR 0387097
9. A. Hajnal, R. Rado, and Vera T. Sós (eds.), Infinite and finite sets. Vols. I, II, III, North-Holland Publishing Co., Amsterdam-London; János Bolyai Mathematical Society, Budapest, 1975. Dedicated to Paul Erdős on his 60th birthday; Colloquia Mathematica Societatis János Bolyai, Vol. 10. MR 0360076
10. Robin Thomas and Xingxing Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994), no. 1, 114–132. MR 1290634, https://doi.org/10.1006/jctb.1994.1058
11. R. Thomas and X. Yu, 5-connected toroidal graphs are hamiltonian. J. Combinat. Theory Ser. B., in press.
12. Carsten Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983), no. 2, 169–176. MR 698698, https://doi.org/10.1002/jgt.3190070205
13. Carsten Thomassen, Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory Ser. B 48 (1990), no. 2, 155–177. MR 1046752, https://doi.org/10.1016/0095-8956(90)90115-G
14. Carsten Thomassen, Trees in triangulations, J. Combin. Theory Ser. B 60 (1994), no. 1, 56–62. MR 1256583, https://doi.org/10.1006/jctb.1994.1005
15. Carsten Thomassen, Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993), no. 1, 89–105. MR 1234386, https://doi.org/10.1006/jctb.1993.1057
16. W. T. Tutte, A theorem on planar graphs. Trans. Amer. Math. Soc. 82 (1956) 99-116. MR 18:408e
17. H. Whitney, A theorem on graphs. Ann. of Math. 32 (1931) 378-390.