Tree-Partitions with Small Bounded Degree Trees

2025-05-06 0 0 164.88KB 12 页 10玖币

侵权投诉

arXiv:2210.12577v2 [math.CO] 28 Jul 2023

Tree-Partitions with Small Bounded Degree Trees∗

Marc Distel ‡David R. Wood ‡

Abstract

Atree-partition of a graph Gis a partition of V(G)such that identifying the

vertices in each part gives a tree. It is known that every graph with treewidth kand

maximum degree ∆has a tree-partition with parts of size O(k∆). We prove the

same result with the extra property that the underlying tree has maximum degree

O(∆) and O(|V(G)|/k)vertices.

1 Introduction

For a graph Gand a tree T, a T-partition of Gis a partition (Vx:x∈V(T)) of V(G)

indexed by the nodes of T, such that for every edge vw of G, if v∈Vxand w∈Vy,

then x=yor xy ∈E(T). The width of a T-partition is max{|Vx|:x∈V(T)}. The

tree-partition-width1of a graph Gis the minimum width of a tree-partition of G.

Tree-partitions were independently introduced by Seese [34] and Halin [26], and have

since been widely investigated [7–9, 16, 17, 23, 35, 36]. Applications of tree-partitions in-

clude graph drawing [13, 15, 21, 22, 37], graphs of linear growth [12], nonrepetitive graph

colouring [3], clustered graph colouring [1, 30], monadic second-order logic [29], network

emulations [4, 5, 10, 24], statistical learning theory [38], size Ramsey numbers [18, 28],

and the edge-Erdős-Pósa property [14, 25, 31]. Tree-partitions are also related to graph

‡School of Mathematics, Monash University, Melbourne, Australia

({marc.distel,david.wood}@monash.edu). Research of D.W. supported by the Australian Re-

search Council. Research of M.D. supported by an Australian Government Research Training Program

Scholarship.

∗July 31, 2023. This work was initiated at the Structural Graph Theory Downunder II workshop at the

Mathematical Research Institute MATRIX (March 2022). A preliminary version of this paper appears in

the 2021-22 MATRIX Annals.

1Tree-partition-width has also been called strong treewidth [8, 34].

product structure theory since a graph Ghas a T-partition of width at most kif and

only if Gis isomorphic to a subgraph of T⊠Kkfor some tree T; see [11, 19, 20] for

example.

Bounded tree-partition-width implies bounded treewidth2, as noted by Seese [34]. In

particular, for every graph G,

tw(G)62 tpw(G)−1.

Of course, tw(T) = tpw(T) = 1 for every tree T. But in general, tpw(G)can be much

larger than tw(G). For example, fan graphs on nvertices have treewidth 2 and tree-

partition-width Ω(√n). On the other hand, the referee of [16] showed that if the maximum

degree and treewidth are both bounded, then so is the tree-partition-width, which is

one of the most useful results about tree-partitions. A graph Gis trivial if E(G) = ∅.

Let ∆(G)be the maximum degree of G.

Theorem 1 ([16]).For any non-trivial graph G,

tpw(G)624(tw(G) + 1)∆(G).

Theorem 1 is stated in [16] with “tw(G)” instead of “tw(G) + 1”, but a close inspection

of the proof shows that “tw(G) + 1” is needed. Wood [36] showed that Theorem 1 is

best possible up to the multiplicative constant, and also improved the constant 24 to

9 + 6√2≈17.48.

This paper proves similar results to Theorem 1 where the tree Tindexing the tree-

partition has two extra properties.

The ﬁrst property is the maximum degree of T. Consider a tree-partition (Bx:x∈V(T))

of a graph Gwith width k. For each node x∈V(T), there are at most Pv∈Bxdeg(v)

edges between Bxand G−Bx. Thus we may assume that degT(x)6|Bx|∆(G)6k∆(G),

otherwise delete an ‘unused’ edge of Tand add an edge to Tbetween leaf vertices of

the resulting component subtrees. It follows that if tpw(G)6kthen Ghas a T-partition

of width at most kfor some tree Twith maximum degree at most max{k∆(G),2}. By

Theorem 1, every graph Ghas a T-partition of width at most 24(tw(G) + 1)∆(G)for

2Atree-decomposition of a graph Gis a collection (Bx⊆V(G) : x∈V(T)) of subsets of V(G)(called

bags) indexed by the nodes of a tree T, such that: (a) for every edge uv ∈E(G), some bag Bxcontains

both uand v; and (b) for every vertex v∈V(G), the set {x∈V(T) : v∈Bx}induces a non-empty

subtree of T. The width of a tree-decomposition is the size of the largest bag, minus 1. The treewidth

of a graph G, denoted by tw(G), is the minimum width of a tree-decomposition of G. Treewidth is the

standard measure of how similar a graph is to a tree. Indeed, a connected graph has treewidth 1 if and

only if it is a tree. Treewidth is of fundamental importance in structural and algorithmic graph theory;

see [6, 27, 32] for surveys.

some tree Twith maximum degree at most 24(tw(G) + 1)∆(G)2. This fact has been

used in several applications of Theorem 1 (see [13, 22] for example).

The second property is the number of vertices in T. This property is motivated by

results about size-Ramsey number by Draganić et al. [18], where tree-partitions of n-

vertex graphs with tw(G)∈O(√n)play a critical role, and it is essential that ∆(T)is

independent of tw(G)and |V(T)| ≪ |V(G)|.

The following theorem improves the above-mentioned upper bound on ∆(T)so that

it is independent of tw(G), and provides a non-trivial upper bound on |V(T)|. Let

N={1,2,...}.

Theorem 2. For any integers k, d ∈N, every non-trivial graph Gwith tw(G)6k−1

and ∆(G)6dhas a T-partition of width at most 18kd, for some tree Twith ∆(T)66d

and |V(T)|6max{|V(G)|

2k,1}.

Theorem 2 enables a tw(G)∆(G)2term to be replaced by a ∆(G)term in various re-

sults [13, 22]. And since ∆(T)is independent of tw(G), and |V(T)| ≪ |V(G)|when

tw(G)is unbounded, Theorem 2 is suitable for the applications to size-Ramsey num-

bers in [18]. Indeed, Theorem 2 improves upon a similar result of Draganić et al. [18,

Lemma 2.1] which has an extra O(log n)factor in the width.

Here we give an example of Theorem 2. Alon, Seymour, and Thomas [2] proved that

every Kt-minor-free graph Ghas treewidth at most t3/2|V(G)|1/2−1. Theorem 2 thus

implies:

Corollary 3. Every Kt-minor-free graph with maximum degree ∆has a T-partition

of width at most 18t3/2∆|V(G)|1/2, for some tree Twith ∆(T)66∆ and |V(T)|6

|V(G)|1/2/2t3/2.

As mentioned above, Wood [36] improved the constant 24 to 9 + 6√2in Theorem 1. By

tweaking the constants in the proof of Theorem 2, we match this constant with a small

increase in the bound on ∆(T); see Section 3. We choose to ﬁrst present the proof with

integer coeﬃcients for ease of understanding.

Our ﬁnal result shows that the linear upper bound on ∆(T)in Theorem 2 is best possible

even for trees.

Proposition 4. For any integer ∆>3there exist α > 0such that there are inﬁnitely

many trees Xwith maximum degree ∆such that for every tree Twith maximum degree

less than ∆, every T-partition of Xhas width at least |V(X)|α. Moreover, if ∆ = 3

then αcan be taken to be arbitrarily close to 1.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.12577v2[math.CO]28Jul2023Tree-PartitionswithSmallBoundedDegreeTrees∗MarcDistel‡DavidR.Wood‡AbstractAtree-partitionofagraphGisapartitionofV(G)suchthatidentifyingtheverticesineachpartgivesatree.Itisknownthateverygraphwithtreewidthkandmaximumdegree∆hasatree-partitionwithpartsofsizeO(k∆).Wepr...

展开>> 收起<<

Tree-Partitions with Small Bounded Degree Trees.pdf

共12页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Tree-Partitions with Small Bounded Degree Trees

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: