Article contents
K5-Subdivisions in Graphs
Published online by Cambridge University Press: 12 September 2008
Abstract
In 1964 Dirac conjectured that every graph with n vertices and at least 3n − 5 edges contains a subdivision of K5 We prove a weakened version with 7/2;n − 7 instead of 3n − 5. We prove that, for any prescribed vertex νo, the subdivision can be found such that νo is not one of the five branch vertices. This variant of Dirac's problem, which was suggested by the present author in 1973, is best possible in the sense that 7/2;n − 7 cannot be replaced by 7/2;n − 15/2;.
- Type
- Research Article
- Information
- Copyright
- Copyright © Cambridge University Press 1996
References
[1]Bondy, J. A. and Lovász, L. (1981) Cycles through specified vertices of a graph. Combinatoric 1 114–140.CrossRefGoogle Scholar
[3]Bollobás, B. and Thomason, A. G.Proof of a conjecture of Mader, Erdös and Hajnal on topological complete subgraphs, Combinatorica, to appear.Google Scholar
[4]Dirac, G. A. (1964) Homomorphism theorems for graphs, Math. Ann. 153 69–80.CrossRefGoogle Scholar
[5]Komlós, J. and Szemerédi, E.Topological cliques in graphs, Combinatorics, Probability and Computing, to appear.Google Scholar
[7]Perfect, H. (1968) Applications of Menger's theorem, J. Math. Analysis Appl. 22 96–111.CrossRefGoogle Scholar
[9]Thomassen, C. (1974) Some homeomorphism properties of graphs, Math. Nachr. 64 119–133.CrossRefGoogle Scholar
[11]Thomassen, C. (1984) Plane representations of graphs, in Progress in Graph Theory, Bondy, J. A. and Murty, U. S. R., eds., Academic Press, pp. 43–69.Google Scholar
[12]Thomassen, C. (1988) Paths circuits and subdivisions, in Selected Topics in Graph Theory, Beineke, L. W. and Wilson, R. J., eds., Academic Press, pp. 97–131.Google Scholar
- 3
- Cited by