Graph minors. V. Excluding a planar graph
From MaRDI portal
Publication:1079583
DOI10.1016/0095-8956(86)90030-4zbMATH Open0598.05055DBLPjournals/jct/RobertsonS86OpenAlexW2057826895WikidataQ56235113 ScholiaQ56235113MaRDI QIDQ1079583FDOQ1079583
Authors: Neil Robertson, Paul Seymour 
Publication date: 1986
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(86)90030-4
Recommendations
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- On rigid circuit graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Graph minors. II. Algorithmic aspects of tree-width
- On Independent Circuits Contained in a Graph
- Title not available (Why is that?)
- A homology theory for spanning tress of a graph
- Graph minors. I. Excluding a forest
- Title not available (Why is that?)
- A characterisation of rigid circuit graphs
- Graph minors. VII: Disjoint paths on a surface
- Ein Planaritaetskriterium für endliche Graphen
- From Matrices to Graphs
Cited In (only showing first 100 items - show all)
- Graph minors. VIII: A Kuratowski theorem for general surfaces
- The structure of the models of decidable monadic theories of graphs
- Random graphs containing few disjoint excluded minors
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Graphs without large apples and the maximum weight independent set problem
- Linearity of grid minors in treewidth with applications through bidimensionality
- Minimum degree conditions for vertex-disjoint even cycles in large graphs
- Edge-disjoint odd cycles in 4-edge-connected graphs
- Boundary properties of graphs for algorithmic graph problems
- The edge-density for \(K_{2,t}\) minors
- The Maximum Independent Set Problem in Planar Graphs
- Algorithmic uses of the Feferman-Vaught theorem
- Minimal classes of graphs of unbounded clique-width
- The disjoint paths problem in quadratic time
- Linkless and flat embeddings in 3-space
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Graph minors. X: Obstructions to tree-decomposition
- Nonrepetitive colorings of graphs
- Recent developments on graphs of bounded clique-width
- Nonrepetitive colorings of graphs of bounded tree-width
- Excluded Forest Minors and the Erdős–Pósa Property
- Rankings of graphs
- Tree-width of graphs without a \(3\times 3\) grid minor
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Linear connectivity forces large complete bipartite minors
- Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
- A partial k-arboretum of graphs with bounded treewidth
- Polynomial treewidth forces a large grid-like-minor
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- The Erdős-Pósa property for clique minors in highly connected graphs
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- Implicit branching and parameterized partial cover problems
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- \(K_{6}\) minors in large 6-connected graphs
- Clique-width of countable graphs: A compactness property.
- Max-Cut and containment relations in graphs
- Directed tree-width
- Tree-width and large grid minors in planar graphs
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- Contraction obstructions for treewidth
- Approximation algorithms for Euler genus and related problems
- Upper bounds to the clique width of graphs
- On the excluded minor structure theorem for graphs of large tree-width
- An edge variant of the Erdős-Pósa property
- Quadratic upper bounds on the Erdős--Pósa property for a generalization of packing and covering cycles
- Random graphs with few disjoint cycles
- Thue type problems for graphs, points, and numbers
- Obtaining a planar graph by vertex deletion
- Graph minors. III. Planar tree-width
- Coloring immersion-free graphs
- Strengthening Erdős -- Pósa property for minor-closed graph classes
- Obstruction set isolation for the gate matrix layout problem
- The structure of graphs not admitting a fixed immersion
- Structural tractability of enumerating CSP solutions
- Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
- Immersion in four-edge-connected graphs
- Tree-width and planar minors
- Rooted grid minors
- A model-theoretic characterisation of clique width
- On embedding graphs in trees
- On the Parameterised Intractability of Monadic Second-Order Logic
- Rank-width and vertex-minors
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- Explicit linear kernels for packing problems
- Jones' conjecture in subcubic graphs
- Planar graph bipartization in linear time
- \(K_{6}\) minors in 6-connected graphs of bounded tree-width
- On search, decision, and the efficiency of polynomial-time algorithms
- Large Induced Subgraphs via Triangulations and CMSO
- Packing cycles through prescribed vertices
- Enumeration of minimal dominating sets and variants
- The monadic second-order logic of graphs. VIII: Orientations
- Excluding infinite minors
- Graph minor theory
- Forbidden subgraphs and graph decomposition
- Graph minors. XVI: Excluding a non-planar graph
- The parameterized complexity of local search for TSP, more refined
- Local search: is brute-force avoidable?
- Minors in graphs of large \(\theta_r\)-girth
- Shortcutting Planar Digraphs
- Nonrepetitive list colourings of paths
- Fixed-parameter tractability of treewidth and pathwidth
- Recognizability in the Simply Typed Lambda-Calculus
- Graphs without two vertex-disjoint \(S\)-cycles
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Tree pivot-minors and linear rank-width
- A new proof of the flat wall theorem
- Layered separators in minor-closed graph classes with applications
- Obstructions for partitioning into forests and outerplanar graphs
- Contraction bidimensionality of geometric intersection graphs
- The edge-Erdős-Pósa property
- Clique-sums, tree-decompositions and compactness
- Induced subgraphs and path decompositions
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Graph minors and parameterized algorithm design
- Canonical representations of partial 2- and 3-trees
- \(K_4\)-subdivisions have the edge-Erdős-Pósa property
This page was built for publication: Graph minors. V. Excluding a planar graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079583)
