Extremal functions for sparse minors
Extremal functions for sparse minors
复制标题
稀疏次要函数的极值函数
DOI：
10.19086/aic.2022.5
复制
发表时间：
2021
影响因子：
--
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
Kevin Hendrey;S. Norin;D. Wood
图子图的概念是现代图论的核心概念，它是图的子图的推广。关于图的子项的经典结果包括图的子项定理和图的结构定理，这两个定理都是由Robertson和Seymour提出的。结果涉及的性质下采取未成年人关闭的图类，这样的图类包括许多重要的自然类的图，例如，平面图类，更一般地说，是可嵌入固定曲面的图类。
图的子定理断言，每一类在取子式下闭的图都有一个有限的禁止子式列表。例如，瓦格纳定理，它声称一个图是平面的当且仅当它不包含或作为一个小的，是这个定理的一个特殊情况。图的结构定理断言，图从一个固定类的图下采取子封闭可以分解成一个树状的方式几乎嵌入在一个固定的表面图。特别是，在一类避免固定子图的图中，每个图都允许强次线性分离器（Lipton和Tarjan的平面分离器定理是这个更一般结果的特殊情况）。
由于包含在一类在取子式下闭的图中的每个图的边数与其顶点数是线性的，因此可以定义为不包含图作为子式的图的最大可能密度。这个数量一直是一个非常深入的研究课题;例如，一长串的界限，以2001年的Escherason的结果而告终，他精确地确定了它的渐近行为。本文给出了当它本身来自一类稀疏图时的界。特别地，证明了一类具有强次线性分离子的图的顶点数和顶点覆盖与顶点数之比的渐近紧界.
The notion of a graph minor, which generalizes graph subgraphs, is a central notion of modern graph theory. Classical results concerning graph minors include the Graph Minor Theorem and the Graph Structure Theorem, both due to Robertson and Seymour. The results concern properties of classes of graphs closed under taking minors; such graph classes include many important natural classes of graphs, e.g., the class of planar graphs and, more generally, the class of graphs embeddable in a fixed surface.
The Graph Minor Theorem asserts that every class of graphs closed under taking minors has a finite list of forbidden minors. For example, Wagner’s Theorem, which claims that a graph is planar if and only if it does not contain or as a minor, is a particular case of this theorem. The Graph Structure Theorem asserts that graphs from a fixed class of graphs closed under taking minors can be decomposed in a tree-like fashion into graphs almost embeddable in a fixed surface. In particular, every graph in a class of graphs avoiding a fixed minor admits strongly sublinear separators (the Planar separator theorem of Lipton and Tarjan is a special case of this more general result).
As the number of edges of every graph contained in a class of graphs closed under taking minors is linear in the number of its vertices, one can define to be the maximum possible density of a graph that does not contain a graph as a minor. This quantity has been a subject of very intensive research; for example, a long list of bounds concerning culminated with a result of Thomason in 2001, who precisely determined its asymptotic behavior. This paper provides bounds on when itself is from a class of sparse graphs. In particular, the authors prove an asymptotically tight bound on in terms of the number of vertices of and the ratio of the vertex cover and the number of vertices of graphs contained in a class of graphs with strongly sublinear separators.