Disjoint paths, planarizing cycles, and spanning walks

Yu, Xingxing

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

Disjoint paths, planarizing cycles, and spanning walks
HTML articles powered by AMS MathViewer

by Xingxing Yu PDF

Trans. Amer. Math. Soc. 349 (1997), 1333-1358 Request permission

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.

References

J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988, DOI 10.1007/978-1-349-03521-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, DOI 10.1006/jctb.1995.1041
Richard A. Duke, On the genus and connectivity of Hamiltonian graphs, Discrete Math. 2 (1972), no. 3, 199–206. MR 314670, DOI 10.1016/0012-365X(72)90003-9
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, DOI 10.1006/jctb.1994.1043
Zhicheng Gao and R. Bruce Richter, $2$-walks in circuit graphs, J. Combin. Theory Ser. B 62 (1994), no. 2, 259–267. MR 1305052, DOI 10.1006/jctb.1994.1068
Branko Grünbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc. 76 (1970), 1131–1201. MR 266050, DOI 10.1090/S0002-9904-1970-12601-5
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, DOI 10.1070/rm1979v034n06abeh003276
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
A. Hajnal, R. Rado, and Vera T. Sós (eds.), Infinite and finite sets. Vols. I, II, III, Colloquia Mathematica Societatis János Bolyai, Vol. 10, North-Holland Publishing Co., Amsterdam-London; János Bolyai Mathematical Society, Budapest, 1975. Dedicated to Paul Erdős on his 60th birthday. MR 0360076
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, DOI 10.1006/jctb.1994.1058
R. Thomas and X. Yu, 5-connected toroidal graphs are hamiltonian. J. Combinat. Theory Ser. B., in press.
Carsten Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983), no. 2, 169–176. MR 698698, DOI 10.1002/jgt.3190070205
Carsten Thomassen, Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory Ser. B 48 (1990), no. 2, 155–177. MR 1046752, DOI 10.1016/0095-8956(90)90115-G
Carsten Thomassen, Trees in triangulations, J. Combin. Theory Ser. B 60 (1994), no. 1, 56–62. MR 1256583, DOI 10.1006/jctb.1994.1005
Carsten Thomassen, Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993), no. 1, 89–105. MR 1234386, DOI 10.1006/jctb.1993.1057
Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
H. Whitney, A theorem on graphs. Ann. of Math. 32 (1931) 378–390.