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.
We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a ...function f:Z+→Z+, such that for every integer g>0, every graph of treewidth at least f(g) contains the (g×g)-grid as a minor. For every integer g>0, let f(g) be the smallest value for which the theorem holds. Establishing tight bounds on f(g) is an important graph-theoretic question. Robertson and Seymour showed that f(g)=Ω(g2logg) must hold. For a long time, the best known upper bounds on f(g) were super-exponential in g. The first polynomial upper bound of f(g)=O(g98polylogg) was proved by Chekuri and Chuzhoy. It was later improved to f(g)=O(g36polylogg), and then to f(g)=O(g19polylogg). In this paper we further improve this bound to f(g)=O(g9polylogg). We believe that our proof is significantly simpler than the proofs of the previous bounds. Moreover, while there are natural barriers that seem to prevent previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this paper can lead to even tighter bounds on f(g).
Planar Graphs Have Bounded Queue-Number Dujmović, Vida; Joret, Gwenaël; Micek, Piotr ...
Journal of the ACM,
08/2020, Letnik:
67, Številka:
4
Journal Article
Recenzirano
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. 66 from 1992. The key to the proof is a new structural tool called
layered partitions
, and the result ...that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number.
Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. 31 that graphs in a proper minor-closed class have low treewidth colourings.
The disjoint paths problem in quadratic time Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce
Journal of combinatorial theory. Series B,
March 2012, 2012-03-00, Letnik:
102, Številka:
2
Journal Article
Recenzirano
Odprti dostop
We consider the following well-known problem, which is called the disjoint paths problem. For a given graph G and a set of k pairs of terminals in G, the objective is to find k vertex-disjoint paths ...connecting given pairs of terminals or to conclude that such paths do not exist. We present an O(n2) time algorithm for this problem for fixed k. This improves the time complexity of the seminal result by Robertson and Seymour, who gave an O(n3) time algorithm for the disjoint paths problem for fixed k. Note that Perković and Reed (2000) announced in 24 (without proofs) that this problem can be solved in O(n2) time. Our algorithm implies that there is an O(n2) time algorithm for the k edge-disjoint paths problem, the minor containment problem, and the labeled minor containment problem. In fact, the time complexity of all the algorithms with the most expensive part depending on Robertson and Seymourʼs algorithm can be improved to O(n2), for example, the membership testing for minor-closed class of graphs.
The Hadwiger number of a graph G, denoted h(G), is the largest integer t such that G contains Kt as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph G, h(G)≥χ(G), ...where χ(G) denotes the chromatic number of G. Let α(G) denote the independence number of G. A graph is H-free if it does not contain the graph H as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that h(G)≥χ(G) for all H-free graphs G with α(G)≤2, where H is any graph on four vertices with α(H)≤2, H=C5, or H is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs H on five vertices with α(H)≤2. In this note, we prove that h(G)≥χ(G) for all W5-free graphs G with α(G)≤2, where W5 denotes the wheel on six vertices.
Hadwiger's conjecture claims that any graph with no
K
t minor is
(
t
−
1
)‐colorable. This has been proved for
t
≤
6, but remains open for
t
≥
7. As a variant of this conjecture, graphs with no
K
t
= ...minor have been considered, where
K
t
= denotes the complete graph with two edges removed. It has been shown that graphs with no
K
t
= minor are
(
2
t
−
8
)‐colorable for
t
∈
{
7
,
8
}. In this paper, we extend this result to the case
t
=
9 and show that graphs with no
K
9
= minor are
10‐colorable.
In this paper, we consider optimal 1-planar multigraphs, that is, n-vertex multigraph having exactly 4n−8 edges and a drawing on the sphere such that each edge crosses at most one other edge, and ...that the drawing has no 2-gonal face. We discuss the connectivity of optimal 1-planar multigraphs, and show a generating theorem of such graphs using some operations preserving optimal 1-planarity. Finally, we characterize optimal 1-planar multigraphs if they have no Kt-minor for t≤7.
We prove a general width duality theorem for combinatorial structures with well-defined notions of cohesion and separation. These might be graphs or matroids, but can be much more general or quite ...different. The theorem asserts a duality between the existence of high cohesion somewhere local and a global overall tree structure.
We describe cohesive substructures in a unified way in the format of tangles: as orientations of low-order separations satisfying certain consistency axioms. These axioms can be expressed without reference to the underlying structure, such as a graph or matroid, but just in terms of the poset of the separations themselves. This makes it possible to identify tangles, and apply our tangle-tree duality theorem, in very diverse settings.
Our result implies all the classical duality theorems for width parameters in graph minor theory, such as path-width, tree-width, branch-width or rank-width. It yields new, tangle-type, duality theorems for tree-width and path-width. It implies the existence of width parameters dual to cohesive substructures such as k-blocks, edge-tangles, or given subsets of tangles, for which no width duality theorems were previously known.
Abstract separation systems can be found also in structures quite unlike graphs and matroids. For example, our theorem can be applied to image analysis by capturing the regions of an image as tangles of separations defined as natural partitions of its set of pixels. It can be applied in big data contexts by capturing clusters as tangles. It can be applied in the social sciences, e.g. by capturing as tangles the few typical mindsets of individuals found by a survey. It could also be applied in pure mathematics, e.g. to separations of compact manifolds.
PDF
