AbstractWe give an exponential upper bound inp4on the size of any obstruction for path-width at mostp. We give a doubly exponential upper bound ink5 on the size of any obstruction for tree-width at mostk. We also give an upper bound on the size of any intertwine of two given treesTandT′. The bound is exponential inO(m2logm) wherem⩽max(|V(T)|, |V(T′)|). Finally, we give an upper bound on the size of any intertwine of two given planar graphsHandH′. This bound is triply exponential inO(m5) wherem⩽max(|V(H)|, |V(H′)|). We introduce the concept ofl-length of a family of graphsL. We prove constructively that, if a minor closed familyLhas finitep-length and has obstructions of path-width at mostp, thenLhas a finite number of obstructions. Our proo...
For their famous algorithm for the disjoint paths problem, Robertson and Seymour proved that there i...
AbstractA bramble in a graph G is a family of connected subgraphs of G such that any two of these su...
AbstractThe graphs with bounded path-width, introduced by Robertson and Seymour, and the graphs with...
AbstractIt is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant ...
AbstractThe Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many nat...
AbstractRoughly, a graph has small “tree-width” if it can be constructed by piecing small graphs tog...
AbstractWe study properties of the sets of minimal forbidden minors for the families of graphs havin...
AbstractA bramble in a graph G is a family of connected subgraphs of G such that any two of these su...
A key theorem in algorithmic graph-minor theory is a min-max relation between the treewidth of a gra...
AbstractThe linear-width of a graph G is defined to be the smallest integer k such that the edges of...
International audienceTree-likeness parameters have proven their utility in the design of efficient ...
International audienceTree-likeness parameters have proven their utility in the design of efficient ...
Let P be a graph with a vertex v such that P-v is a forest and let Q be an outerplanar graph. In 199...
AbstractThe Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many nat...
AbstractWe prove that for any fixed r≥2, the tree-width of graphs not containing Kr as a topological...
For their famous algorithm for the disjoint paths problem, Robertson and Seymour proved that there i...
AbstractA bramble in a graph G is a family of connected subgraphs of G such that any two of these su...
AbstractThe graphs with bounded path-width, introduced by Robertson and Seymour, and the graphs with...
AbstractIt is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant ...
AbstractThe Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many nat...
AbstractRoughly, a graph has small “tree-width” if it can be constructed by piecing small graphs tog...
AbstractWe study properties of the sets of minimal forbidden minors for the families of graphs havin...
AbstractA bramble in a graph G is a family of connected subgraphs of G such that any two of these su...
A key theorem in algorithmic graph-minor theory is a min-max relation between the treewidth of a gra...
AbstractThe linear-width of a graph G is defined to be the smallest integer k such that the edges of...
International audienceTree-likeness parameters have proven their utility in the design of efficient ...
International audienceTree-likeness parameters have proven their utility in the design of efficient ...
Let P be a graph with a vertex v such that P-v is a forest and let Q be an outerplanar graph. In 199...
AbstractThe Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many nat...
AbstractWe prove that for any fixed r≥2, the tree-width of graphs not containing Kr as a topological...
For their famous algorithm for the disjoint paths problem, Robertson and Seymour proved that there i...
AbstractA bramble in a graph G is a family of connected subgraphs of G such that any two of these su...
AbstractThe graphs with bounded path-width, introduced by Robertson and Seymour, and the graphs with...