Contractible Subgraphs in 3-Connected Graphs
Contractible Subgraphs in 3-Connected Graphs
复制标题
三连通图中的可收缩子图
DOI：
10.1006/jctb.2000.1960
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
M. Kriesell
中科院分区：
文献类型：
--
作者：
M. Kriesell
一个3-连通有限图G的子图H称为可收缩图，如果H是连通的，且G？V（H）是2连通的。McCuaig和Ota提出了一个猜想，即对任意给定的k，存在一个f（k）使得至少f（k）个顶点上的任意3-连通图在k个顶点上有一个可收缩子图.我们证明了这一点，k？4，并考虑对极大平面图、Halin图、6-边连通图的线图、有界度的5-连通图和AT-自由图的限制。
A subgraph H of a 3-connected finite graph G is called contractible if H is connected and G?V(H) is 2-connected. This work is concerned with a conjecture of McCuaig and Ota which states that for any given k there exists an f(k) such that any 3-connected graph on at least f(k) vertices possesses a contractible subgraph on k vertices. We prove this for k?4 and consider restrictions to maximal planar graphs, Halin graphs, line graphs of 6-edge-connected graphs, 5-connected graphs of bounded degree, and AT-free graphs.