Graph minors. XX: Wagner's conjecture
From MaRDI portal
Publication:705888
DOI10.1016/j.jctb.2004.08.001zbMath1061.05088OpenAlexW2067016370WikidataQ55934687 ScholiaQ55934687MaRDI QIDQ705888
Publication date: 16 February 2005
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2004.08.001
Hypergraphs (05C65) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Graph minors (05C83)
Related Items
Definability in First Order Theories of Graph Orderings, Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Computing Tree Decompositions, A Retrospective on (Meta) Kernelization, A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH, Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Obstructions to within a few vertices or edges of acyclic, Minimum Degree and Graph Minors, A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, Properties of Large 2-Crossing-Critical Graphs, Interview with Don Knuth, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Spined categories: generalizing tree-width beyond graphs, Classifying intrinsically linked tournaments by score sequence, From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals, Edge-treewidth: algorithmic and combinatorial properties, Clique minors in graphs with a forbidden subgraph, Connected search for a lazy robber, First-order Logic with Connectivity Operators, Arkhipov's theorem, graph minors, and linear system nonlocal games, Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width, A full characterization of invariant embeddability of unimodular planar graphs, Branchwidth is \((1, g)\)-self-dual, Complete minors in complements of nonseparating planar graphs, Packing topological minors half‐integrally, On the logical strength of the better quasi order with three elements, The graph minor theorem in topological combinatorics, Critical properties of bipartite permutation graphs, Excluding a planar matching minor in bipartite graphs, Well-quasi-ordering Friedman ideals of finite trees proof of Robertson's magic-tree conjecture, Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality, Parameterized Counting and Cayley Graph Expanders, A survey of parameterized algorithms and the complexity of edge modification, Unnamed Item, Unnamed Item, Unnamed Item, Finding geometric representations of apex graphs is \textsf{NP}-hard, Unnamed Item, Unnamed Item, Unnamed Item, Graphs of large chromatic number, Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Induced minors and well-quasi-ordering, Classical Ising model test for quantum circuits, Nerves, minors, and piercing numbers, Unnamed Item, Hybrid Tractable Classes of Constraint Problems, SOME RESULTS ON INTRINSICALLY KNOTTED GRAPHS, Excluded Forest Minors and the Erdős–Pósa Property, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Random graphs containing few disjoint excluded minors, An Algorithm for Detecting Intrinsically Knotted Graphs, Logarithmically small minors and topological minors, A polynomial algorithm for recognizing bounded cutwidth in hypergraphs, A Short Derivation of the Structure Theorem for Graphs with Excluded Topological Minors, The communication complexity of enumeration, elimination, and selection, Clique-width and well-quasi-ordering of triangle-free graph classes, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Unnamed Item, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, Morphisms of Neural Codes, Combinatorics and algorithms for quasi-chain graphs, Block elimination distance, When Is the Matching Polytope Box-Totally Dual Integral?, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Positive-Instance Driven Dynamic Programming for Treewidth., A Linear-Time Parameterized Algorithm for Node Unique Label Cover, Shorter Labeling Schemes for Planar Graphs, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Atomicity and Well Quasi-Order for Consecutive Orderings on Words and Permutations, Log-Concavity of Combinations of Sequences and Applications to Genus Distributions, Unnamed Item, Tree Pivot-Minors and Linear Rank-Width, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, Critical elements in combinatorially closed families of graph classes, Bipartite Intrinsically Knotted Graphs with 22 Edges, An algorithmic metatheorem for directed treewidth, Trees, grids, and MSO decidability: from graphs to matroids, Looking at the stars, The micro-world of cographs, Excluded-minor characterization of apex-outerplanar graphs, Ribbon graph minors and low-genus partial duals, Contraction obstructions for connected graph searching, Posets with cover graph of pathwidth two have bounded dimension, Toric geometry of cuts and splits, Scattered packings of cycles, On the graph condition regarding the \(F\)-inverse cover problem, An universality argument for graph homomorphisms, Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors, Obstructions for two-vertex alternating embeddings of graphs in surfaces, Coloring immersion-free graphs, Minimal universal and dense minor closed classes, Quickly deciding minor-closed parameters in general graphs, Vertex-minors, monadic second-order logic, and a conjecture by Seese, On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture, Characterizing width two for variants of treewidth, Minors and dimension, Intrinsic linking and knotting of graphs in arbitrary 3-manifolds, Obstructions for embedding cubic graphs on the spindle surface, Transforms and minors for binary functions, Well-quasi-order of relabel functions, Some recent progress and applications in graph minor theory, Boundary properties of well-quasi-ordered sets of graphs, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Reoptimization of maximum weight induced hereditary subgraph problems, Intrinsic linking in directed graphs, Effective computation of immersion obstructions for unions of graph classes, A minimum degree condition forcing complete graph immersion, Labelled induced subgraphs and well-quasi-ordering, A well-quasi-order for tournaments, Rao's degree sequence conjecture, A decidability result for the dominating set problem, On self-duality of branchwidth in graphs of bounded genus, Outerplanar obstructions for a feedback vertex set, Forbidden graphs for tree-depth, Minor relations for quadrangulations on the sphere, On graph contractions and induced minors, The minimum semidefinite rank of the complement of partial \(k\)-trees, Linkless and flat embeddings in 3-space, Intrinsically linked signed graphs in projective space, The maximal linear extension theorem in second order arithmetic, Well-quasi-ordering of matrices under Schur complement and applications to directed graphs, Grid classes and partial well order, Locally constrained graph homomorphisms -- structure, complexity, and applications, The saga of minimum spanning trees, Faster parameterized algorithms for minor containment, Canonical antichains of unit interval and bipartite permutation graphs, Confronting intractability via parameters, On structural descriptions of lower ideals of series parallel posets, The kernelization complexity of connected domination in graphs with (no) small cycles, Metric uniformization and spectral bounds for graphs, Forbidden minors for graphs with no first obstruction to parametric Feynman integration, Complete monotonicity for inverse powers of some combinatorially defined polynomials, Chromatic number and complete graph substructures for degree sequences, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, Computing tree-depth faster than \(2^n\), A simple linear-time algorithm for finding path-decompositions of small width, Fixed-parameter tractability and completeness II: On completeness for W[1], Mixed searching and proper-path-width, Odd complete minors in even embeddings on surfaces, Forbidden directed minors and Kelly-width, Advice classes of parametrized tractability, Theta rank, levelness, and matroid minors, Excluding infinite minors, Complete graph immersions in dense graphs, Some open problems on excluding a uniform matroid, The strong Arnold property for 4-connected flat graphs, Ramsey numbers of cubes versus cliques, Connected graph searching, Every minor-closed property of sparse graphs is testable, On obstructions to small face covers in planar graphs, Graph minors XXIII. Nash-Williams' immersion conjecture, Finite planar emulators for \(K_{4,5} - 4K_{2}\) and \(K_{1,2,2,2}\) and Fellows' conjecture, When excluding one matroid prevents infinite antichains, Growth constants of minor-closed classes of graphs, Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs, Single source shortest paths in \(H\)-minor free graphs, Well-quasi-ordering versus clique-width: new results on bigenic classes, Explicit bounds for graph minors, Well-structured graph transformation systems, The complexity ecology of parameters: An illustration using bounded max leaf number, Universality of intervals of line graph order, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope, On the subgraph epimorphism problem, A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem, On canonical antichains, Linearizing well quasi-orders and bounding the length of bad sequences, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Graph minors. XXI. graphs with unique linkages, 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, Nested cycles in large triangulations and crossing-critical graphs, Finite dualities and map-critical graphs on a fixed surface, Combinatorial optimization with 2-joins, Minor-obstructions for apex sub-unicyclic graphs, Stabilizer theorems for even cycle matroids, Unnamed Item, Some notes on bounded starwidth graphs, On Flattenability of Graphs, On the Pathwidth of Almost Semicomplete Digraphs, Unnamed Item, A survey on combinatorial optimization in dynamic environments, Fixed-Parameter Tractability, A Prehistory,, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, What’s Next? Future Directions in Parameterized Complexity, Unnamed Item, Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model, Framed 4-valent graph minor theory II: Special minors and new examples, A Polynomial-Time Algorithm for Outerplanar Diameter Improvement, Finding cycles and trees in sublinear time, Framed 4-valent graph minor theory I: Introduction. A planarity criterion and linkless embeddability, Polynomial-time self-reducibility: theoretical motivations and practical results∗, The minor minimal intrinsically chiral graphs, Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs, Integer packing sets form a well-quasi-ordering, A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion, A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three, Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets, Well-quasi-ordering \(H\)-contraction-free graphs, Characterizing graphs of maximum matching width at most 2, Maximum matching width: new characterizations and a fast algorithm for dominating set, Infinitely many minimal classes of graphs of unbounded clique-width, Local 2-separators, Clique immersions and independence number, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, TRIANGLE-Y EXCHANGES ON INTRINSIC KNOTTING OF ALMOST COMPLETE AND COMPLETE PARTITE GRAPHS, Wheel-Free Deletion Is W[2-Hard], Family sizes for complete multipartite graphs, Positive-instance driven dynamic programming for treewidth, Mineurs d'arbres avec racines, Obtaining a Planar Graph by Vertex Deletion, Recognizing small subgraphs, Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices, Applying the Graph Minor Theorem to the Verification of Graph Transformation Systems, On strict brambles, Obtaining a planar graph by vertex deletion, Triangle-free projective-planar graphs with diameter two: domination and characterization, Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\), Graph theory. Abstracts from the workshop held January 2--8, 2022, The Excluded Minors for Isometric Realizability in the Plane, Square roots of minor closed graph classes, MINORS IN WEIGHTED GRAPHS, QUBO formulation for the contact map overlap problem, Many, many more intrinsically knotted graphs, Finite automata as characterizations of minor closed tree families (extended abstract), Well, Better and In-Between, The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings, Upper Bounds on the Graph Minor Theorem, Recent Progress on Well-Quasi-ordering Graphs, Well-Quasi Orders and Hierarchy Theory, The size of an intertwine, Vertex-minor reductions can simulate edge contractions, Recent developments in spatial graph theory, Order nine MMIK graphs, The 𝐾_{𝑛+5} and 𝐾_{3²,1ⁿ} families and obstructions to 𝑛-apex., Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension, Arbitrary Overlap Constraints in Graph Packing Problems, The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed, Obstruction sets for outer-cylindrical graphs, Bipartite induced subgraphs and well-quasi-ordering, CONTEXT-FREE GROUPS AND THEIR STRUCTURE TREES, Unnamed Item, Unnamed Item, REGULAR PROJECTIONS OF GRAPHS WITH AT MOST THREE DOUBLE POINTS, Graphs and obstructions in four dimensions., Sublinear Graph Approximation Algorithms, More intrinsically knotted graphs with 22 edges and the restoring method, INTRINSICALLY KNOTTED GRAPHS HAVE AT LEAST 21 EDGES, Excluded Minors and the Ribbon Graphs of Knots, Graph minor theory, On tree width, bramble size, and expansion, Excluding a group-labelled graph, On self‐immersions of infinite graphs, Cut Dominants and Forbidden Minors, Enumeration of Minimal Dominating Sets and Variants, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes, A Structure Theorem for Strong Immersions, Well-quasi-ordering Does Not Imply Bounded Clique-width, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, FPT is characterized by useful obstruction sets, A Polynomial Time Algorithm for Bounded Directed Pathwidth, On possible counterexamples to Negami's planar cover conjecture, Kernelization: New Upper and Lower Bound Techniques, Graph classes with given 3-connected components: Asymptotic enumeration and random graphs, REOPTIMIZATION UNDER VERTEX INSERTION: MAX Pk-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH, Tournaments and Semicomplete Digraphs, GRAPHS WITH A KNOT OR 3-COMPONENT LINK IN EVERY SPATIAL EMBEDDING, Outerplanar Obstructions for the Feedback Vertex Set, Obstructions for Tree-depth, Well-quasi-ordering hereditarily finite sets, Variations on a theme of Kuratowski, Knots and links in spatial graphs: a survey, Matroids Determine the Embeddability of Graphs in Surfaces, On Vertex Partitions and the Colin de Verdière Parameter, A polynomial excluded-minor approximation of treedepth, On the critical densities of minor-closed classes, Improved self-reduction algorithms for graphs with bounded treewidth, Obstruction set isolation for the gate matrix layout problem, On the complexity of finite subgraphs of the curve graph, Large immersions in graphs with independence number 3 and 4, A linear time algorithm for monadic querying of indefinite data over linearly ordered domains, Tree-width dichotomy, Diagonal flips in triangulations of surfaces, Binary constraint satisfaction problems defined by excluded topological minors, An infinite antichain of planar tanglegrams, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, Excluded checkerboard colourable ribbon graph minors, On the invariance of Colin de Verdière's graph parameter under clique sums, Biased graphs. VII: Contrabalance and antivoltages, A minor-monotone graph parameter based on oriented matroids, Computable linearizations of well-partial-orderings, Finding geometric representations of apex graphs is NP-hard, Intrinsically linked graphs in projective space, Redundancy in logic. II: 2CNF and Horn propositional formulae, The rank-width of edge-coloured graphs, On the number of cliques in graphs with a forbidden minor, Bipartite intrinsically knotted graphs with 23 edges, Tree-width and dimension, A new intrinsically knotted graph with 22 edges, A polynomial-time algorithm for outerplanar diameter improvement, Rank-width: algorithmic and structural results, Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions, Sparse obstructions for minor-covering parameters, The obstructions of a minor-closed set of graphs defined by a context-free grammar, WQO is decidable for factorial languages, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, Fixed-parameter tractable distances to sparse graph classes, The \(k\)-strong induced arboricity of a graph, The complexity of generalized graph colorings, One-third-integrality in the max-cut problem, The circumference of a graph with no \(K_{3,t}\)-minor. II, Six variations on a theme: almost planar graphs, On immersions of uncountable graphs, An algorithm for delta-wye reduction of almost-planar graphs, The forbidden minor characterization of line-search antimatroids of rooted digraphs, Filtration simplification for persistent homology via edge contraction, Ideals of graph homomorphisms, Some connectivity properties for excluded minors of the graph invariant \(\nu(G)\), \(\mathcal{P}\)-apex graphs, Graph theory in Coq: minors, treewidth, and isomorphisms, On the purity of minor-closed classes of graphs, Graph minors. XIX: Well-quasi-ordering on a surface., How to compute digraph width measures on directed co-graphs, Dickson's lemma, Higman's theorem and beyond: a survey of some basic results in order theory, Non-separating planar graphs, All minor-minimal apex obstructions with connectivity two, Well-quasi-ordering versus clique-width, Four-searchable biconnected outerplanar graphs, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, A branch-and-price-and-cut method for computing an optimal bramble, On compatibility and incompatibility of collections of unrooted phylogenetic trees, A new graph parameter related to bounded rank positive semidefinite matrix completions, Multigraded commutative algebra of graph decompositions, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, Fast minor testing in planar graphs, On the geometric Ramsey number of outerplanar graphs, Dichotomy results for fixed point counting in Boolean dynamical systems, A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families, On the structure of \(k\)-connected graphs without \(K_{k}\)-minor, Split permutation graphs, Fractal classes of matroids, Two forbidden induced subgraphs and well-quasi-ordering, Multibranched surfaces in 3-manifolds, On perturbations of highly connected dyadic matroids, Toroidal grid minors and stretch in embedded graphs, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Role colouring graphs in hereditary classes, Unavoidable minors for graphs with large \(\ell_p\)-dimension, Minor obstructions for apex-pseudoforests, Critical properties and complexity measures of read-once Boolean functions, Extension complexity of the correlation polytope, Upper bounds on the size of obstructions and intertwines, A partial k-arboretum of graphs with bounded treewidth, On width measures and topological problems on semi-complete digraphs, Matroids, delta-matroids and embedded graphs, Conformal growth rates and spectral geometry on distributional limits of graphs, Excluding any graph as a minor allows a low tree-width 2-coloring, On computing graph minor obstruction sets, Local certification of graphs on surfaces, The poset of graphs ordered by induced containment, Transformations in closed 2-cell embeddings on surfaces preserving specified properties, Finding small-width connected path decompositions in polynomial time, Chirality for simple graphs of size up to 12, Remarks on a paper of J. Barát and P.P. Varjú, Graphs with magnetic Schrödinger operators of low corank, Diagonal flips in triangulations on closed surfaces with minimum degree at least 4, Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation, Tournament minors, Hereditary classes of graphs: a parametric approach, \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method, On the immersion relation and an embedding problem for infinite graphs, Complexity of protein folding, On well quasi-order of graph classes under homomorphic image orderings
Cites Work
