Almost all 3-connected graphs contain a contractible set of k vertices

Authors
Kriesell, M
Citation
M. Kriesell, Almost all 3-connected graphs contain a contractible set of k vertices, J COMB TH B, 83(2), 2001, pp. 305-319
Citations number
6
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
83
Issue
2
Year of publication
2001
Pages
305 - 319
Database
ISI
SICI code
0095-8956(200111)83:2<305:AA3GCA>2.0.ZU;2-U
Abstract
McCuaig and Ota conjectured that every sufficiently large 3-connected graph G contains a connected subgraph H on k vertices such that G - V(H) is 2-co nnected. We prove the weaker statement that every sufficiently large 3-conn ected graph G contains a not necessarily connected subgraph H on k vertices such that G - V(H) is 2-connected. (C) 2001 Academic Press.