Graph minors. XVI: Excluding a non-planar graph

DOI10.1016/S0095-8956(03)00042-XzbMath1023.05040OpenAlexW2035409201WikidataQ56235114 ScholiaQ56235114MaRDI QIDQ1410731

Publication date: 15 October 2003

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0095-8956(03)00042-x

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Related Items

Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth, Labelings vs. embeddings: on distributed and prioritized representations of distances, Shallow Minors, Graph Products, and Beyond-Planar Graphs, Packing topological minors half‐integrally, 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, Approximating sparse quadratic programs, Induced subgraphs and tree decompositions V. one neighbor in a hole, Isomorphism Testing for Graphs Excluding Small Minors, Clustered 3-colouring graphs of bounded degree, Characterising bounded expansion by neighbourhood complexity, A note on multiflows and treewidth, Forcing a K_r minor by high external connectivity, Excluding subdivisions of bounded degree graphs, Grids and their minors, Fixed-Parameter Tractability of Treewidth and Pathwidth, A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes, Minors and dimension, Layered separators in minor-closed graph classes with applications, Some recent progress and applications in graph minor theory, Forbidding Kuratowski Graphs as Immersions, A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three, Approximation Algorithms for Euler Genus and Related Problems, Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets, Effective computation of immersion obstructions for unions of graph classes, On the excluded minor structure theorem for graphs of large tree-width, Improved FPT algorithms for weighted independent set in bull-free graphs, An Improved Algorithm for Finding Cycles Through Elements, The disjoint paths problem in quadratic time, The Erdős-Pósa property for clique minors in highly connected graphs, Classes of graphs with small rank decompositions are \(\chi \)-bounded, Parameterized complexity of finding small degree-constrained subgraphs, Long induced paths in minor-closed graph classes and beyond, Grad and classes with bounded expansion. I: Decompositions, Grad and classes with bounded expansion. II: Algorithmic aspects, Local search is a PTAS for feedback vertex set in minor-free graphs, Unnamed Item, Approximation algorithms via contraction decomposition, Graph theory. Abstracts from the workshop held January 2--8, 2022, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, Templates for Binary Matroids, Unnamed Item, Local search: is brute-force avoidable?, Catalan structures and dynamic programming in \(H\)-minor-free graphs, A unified approach to distance-two colouring of graphs on surfaces, Distance-two coloring of sparse graphs, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Subexponential parameterized algorithms, Partitioning \(H\)-minor free graphs into three subgraphs with no large components, Dominating set is fixed parameter tractable in claw-free graphs, Tangle-tree duality in abstract separation systems, Spanners in sparse graphs, Implicit branching and parameterized partial cover problems, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Graph minors. X: Obstructions to tree-decomposition, Orthogonal Tree Decompositions of Graphs, First-Order Model-Checking in Random Graphs and Complex Networks, Explicit linear kernels for packing problems, Polynomial bounds for centered colorings on proper minor-closed graph classes, Partitioning \(H\)-minor free graphs into three subgraphs with no large components, Linearity of grid minors in treewidth with applications through bidimensionality, Four-searchable biconnected outerplanar graphs, Some open problems on excluding a uniform matroid, A new proof of the flat wall theorem, Improved Bounds for Centered Colorings, Sparse covers for planar graphs and graphs that exclude a fixed minor, Additive non-approximability of chromatic number in proper minor-closed classes, Parameterized complexity of the spanning tree congestion problem, On the structure of \(k\)-connected graphs without \(K_{k}\)-minor, Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs, Contraction obstructions for treewidth, A Short Derivation of the Structure Theorem for Graphs with Excluded Topological Minors, Excluding a large theta graph, Explicit bounds for graph minors, On low rank-width colorings, Finding cactus roots in polynomial time, Computing with Tangles, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, The Matroid Secretary Problem for Minor-Closed Classes and Random Matroids, Graph minor theory, Excluding a group-labelled graph, Covering nearly surface-embedded graphs with a fixed number of balls, Circle graph obstructions under pivoting, Notes on graph product structure theory, A Structure Theorem for Strong Immersions, Hadwiger’s Conjecture, Linear connectivity forces large complete bipartite minors, Graph minors. XXI. graphs with unique linkages, Tangles, tree-decompositions and grids in matroids, A partial k-arboretum of graphs with bounded treewidth, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, Graph minors. XVII: Taming a vortex, Excluding any graph as a minor allows a low tree-width 2-coloring, Dynamic programming for graphs on surfaces, On the Path Separability of Planar Graphs, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Graph minors. I. Excluding a forest, Excluding a countable clique, Additive non-approximability of chromatic number in proper minor-closed classes, Unnamed Item, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Graph minors. III. Planar tree-width, The Grad of a Graph and Classes with Bounded Expansion, Fraternal Augmentations of graphs, Coloration and Minors, Simple PTAS's for families of graphs excluding a minor

Cites Work