Graph minors. V. Excluding a planar graph

DOI10.1016/0095-8956(86)90030-4zbMath0598.05055OpenAlexW2057826895WikidataQ56235113 ScholiaQ56235113MaRDI QIDQ1079583

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

zbMATH Keywords

planar graphs tree-width graph minors contraction of subgraphs Minors of graphs

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (only showing first 100 items - show all)

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Constant Congestion Brambles in Directed Graphs ⋮ Treewidth of Cartesian Products of Highly Connected Graphs ⋮ Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Characterising graphs with no subdivision of a wheel of bounded diameter ⋮ $k$-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width ⋮ Approximating Pathwidth for Graphs of Small Treewidth ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ Even A‐cycles have the edge‐Erdős–Pósa property ⋮ First-order Logic with Connectivity Operators ⋮ The complexity of learning minor closed graph classes ⋮ Erdős–Pósa property of obstructions to interval graphs ⋮ Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ Graphs of linear growth have bounded treewidth ⋮ Packing topological minors half‐integrally ⋮ Critical properties of bipartite permutation graphs ⋮ Excluding a planar matching minor in bipartite graphs ⋮ Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree ⋮ Induced subgraphs and tree decompositions. VII: Basic obstructions in $H$-free graphs ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Induced subgraphs and path decompositions ⋮ Rankings of graphs ⋮ A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups ⋮ Induced subgraphs and tree decompositions V. one neighbor in a hole ⋮ The monadic second-order logic of graphs : Definable sets of finite graphs ⋮ Unnamed Item ⋮ A Tight Erdös--Pósa Function for Wheel Minors ⋮ Erdös--Pósa from Ball Packing ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Deciding whether a grid is a topological subgraph of a planar graph is NP-complete ⋮ Excluded Forest Minors and the Erdős–Pósa Property ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. ⋮ Random graphs containing few disjoint excluded minors ⋮ Obstructions for Bounded Branch-depth in Matroids ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ Unnamed Item ⋮ Lower bounds for strictly fundamental cycle bases in grid graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Subcritical Graph Classes Containing All Planar Graphs ⋮ Unnamed Item ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Elimination Distance to Bounded Degree on Planar Graphs ⋮ Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms ⋮ Nonrepetitive colorings of graphs ⋮ Nonrepetitive colorings of graphs ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Packing and Covering Induced Subdivisions ⋮ Erdös--Pósa Property for Labeled Minors: 2-Connected Minors ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Excluding a Substar and an Antisubstar ⋮ $K_4$-Subdivisions Have the Edge-Erdös--Pósa Property ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Unnamed Item ⋮ Faster 3-Coloring of Small-Diameter Graphs ⋮ Tree Pivot-Minors and Linear Rank-Width ⋮ Critical elements in combinatorially closed families of graph classes ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side ⋮ The edge-Erdős-Pósa property ⋮ Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ An edge variant of the Erdős-Pósa property ⋮ Fast partitioning $l$-apex graphs with applications to approximating maximum induced-subgraph problems ⋮ Obstruction set isolation for the gate matrix layout problem ⋮ Obstructions for partitioning into forests and outerplanar graphs ⋮ Induced and weak induced arboricities ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ A polynomial time algorithm for strong edge coloring of partial $k$-trees ⋮ Computing crossing numbers in quadratic time ⋮ On search, decision, and the efficiency of polynomial-time algorithms ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Reduction rules for the maximum parsimony distance on phylogenetic trees ⋮ A Menger-like property of tree-width: The finite case ⋮ Grids and their minors ⋮ Coloring immersion-free graphs ⋮ On embedding graphs in trees ⋮ A simpler proof of the excluded minor theorem for higher surfaces ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Rooted grid minors ⋮ On tree-partitions of graphs ⋮ The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Some recent progress and applications in graph minor theory ⋮ The parameterized complexity of local search for TSP, more refined ⋮ On interval routing schemes and treewidth ⋮ On the excluded minor structure theorem for graphs of large tree-width ⋮ The edge-density for $K_{2,t}$ minors ⋮ Improved bounds on the planar branchwidth with respect to the largest grid minor size ⋮ $K_4$-expansions have the edge-Erdős-Pósa property

Cites Work

This page was built for publication: Graph minors. V. Excluding a planar graph