Abstract
In 1964 Dirac conjectured that every graph with 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 v0 the subdivision can be found such that v0 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.
Original language | English |
---|---|
Journal | Combinatorics, Probability & Computing |
Volume | 5 |
Issue number | 2 |
Pages (from-to) | 179-189 |
ISSN | 0963-5483 |
DOIs | |
Publication status | Published - 1996 |