Graph minor theory

DOI10.1090/S0273-0979-05-01088-8zbMath1082.05082WikidataQ29037774 ScholiaQ29037774MaRDI QIDQ3372389

No author found.

Publication date: 20 February 2006

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

planar graphsminor-closed class of graphs

Mathematics Subject Classification ID

Graph minors (05C83)

Related Items (46)

Neighborhood contraction in graphs ⋮ Linearity is strictly more powerful than contiguity for encoding graphs ⋮ Belief propagation and loop series on planar graphs ⋮ Linearity Is Strictly More Powerful Than Contiguity for Encoding Graphs ⋮ On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Framed 4-valent graph minor theory II: Special minors and new examples ⋮ Approximation of the Quadratic Knapsack Problem ⋮ On the pathwidth of hyperbolic 3-manifolds ⋮ Framed 4-valent graph minor theory I: Introduction. A planarity criterion and linkless embeddability ⋮ P-RAM vs. RP-RAM ⋮ Genera and minors of multibranched surfaces ⋮ (Nearly-)tight bounds on the contiguity and linearity of cographs ⋮ The circumference of a graph with no \(K_{3,t}\)-minor. II ⋮ Clique minors in graphs with a forbidden subgraph ⋮ New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023 ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Quantum routing in planar graph using perfect state transfer ⋮ The complexity of two graph orientation problems ⋮ Super domination: graph classes, products and enumeration ⋮ Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs ⋮ Unnamed Item ⋮ Pathwidth, trees, and random embeddings ⋮ Weakly distinguishing graph polynomials on addable properties ⋮ Square roots of minor closed graph classes ⋮ The saga of minimum spanning trees ⋮ MINORS IN WEIGHTED GRAPHS ⋮ The average cut-rank of graphs ⋮ The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings ⋮ Testing outerplanarity of bounded degree graphs ⋮ Positive braids of maximal signature ⋮ Every minor-closed property of sparse graphs is testable ⋮ Unnamed Item ⋮ REGULAR PROJECTIONS OF GRAPHS WITH AT MOST THREE DOUBLE POINTS ⋮ Two-Planar Graphs Are Quasiplanar ⋮ Single source shortest paths in \(H\)-minor free graphs ⋮ Unnamed Item ⋮ On the subgraph epimorphism problem ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited ⋮ Combinatorial optimization with 2-joins ⋮ Metrically homogeneous graphs of diameter 3 ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Graph minors. III. Planar tree-width
• The strong perfect graph theorem
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Decomposition of regular matroids
• Disjoint paths in graphs
• 2-linked graphs
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
• Graph minors. XIX: Well-quasi-ordering on a surface.
• Graph minors. XVII: Taming a vortex
• Decomposition of balanced matrices
• Graph minors. IX: Disjoint crossed paths
• A Kuratowski theorem for nonorientable surfaces
• Balanced \(0,\pm 1\) matrices. I: Decomposition
• Graph minors. XIII: The disjoint paths problem
• Sachs' linkless embedding conjecture
• Automorphism groups of graphs and edge-contraction
• The theory of well-quasi-ordering: a frequently discovered concept
• Highly linked graphs
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Graph minors and linkages
• Lectures on matroids
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: Graph minor theory