2017/04/02 by M. N. Ellingham, Ellingham, M. N., Songling Shan +5
Mathematics · #05C42 (05C05 05C10 05C45) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C10 #msc:05C42
paper · pdf · doi:10.48550/arxiv.1704.00246
Proposition 2.3 in v1 was incorrect; this has been fixed. 25 pages, 1 figure
arxiv created 2019/07/01 · arxiv updated 2019/07/02
For an integer k, a k-tree is a tree with maximum degree at most k. More generally, if f is an integer-valued function on vertices, an f-tree is a tree in which each vertex v has degree at most f(v). Let c(G) denote the number of components of a graph G. We show that if G is a connected K4-minor-free graph and c(G-S) ≤ ∑v ∈ S (f(v)-1) \hboxfor all S ⊆ V(G) with S ≠ ∅ then G has a spanning f-tree. Consequently, if G is a (1)/(k-1)-tough K4-minor-free graph, then G has a spanning k-tree. These results are stronger than results for general graphs due to Win (for k-trees) and Ellingham, Nam and Voss (for f-trees). The K4-minor-free graphs form a subclass of planar graphs, and are identical to graphs of treewidth at most 2, and also to graphs whose blocks are series-parallel. We provide examples to show that the inequality above cannot be relaxed by adding 1 to the right-hand side, and also to show that our result does not hold for general planar graphs. Our proof uses a technique where we incorporate toughness-related information into weights associated with vertices and cutsets.