Some recent progress and applications in graph minor theory

DOI10.1007/S00373-006-0684-XzbMATH Open1114.05096OpenAlexW2039732465MaRDI QIDQ878052FDOQ878052

Ken-ichi Kawarabayashi, Bojan Mohar

Publication date: 26 April 2007

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-006-0684-x

zbMATH Keywords

ConnectivityTree-widthTree-decompositionComplete bipartite minorComplete graph minorExcluded minorGraphs on surfacesGrid minorHadwiger ConjectureNear embeddingPath-decompositionVortex structure

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph minors (05C83)

Cites Work

• Graph minors. XVII: Taming a vortex
• Graph minors. XII: Distance on a surface
• Graph minors. XIV: Extending an embedding
• Parallel complexity of partitioning a planar graph into vertex-induced forests
• Graph minors. XI: Circuits on a surface
• Kuratowski chains
• Sachs' linkless embedding conjecture
• Graph minors. XV: Giant steps
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• Topological subgraphs in graphs of large girth
• Minors in graphs of large girth
• Girth in graphs
• Efficient algorithms for vertex arboricity of planar graphs
• On the presence of disjoint subgraphs of a specified type
• Coloring-flow duality of embedded graphs
• Graph minors. IV: Tree-width and well-quasi-ordering
• Multiple-source shortest paths in planar graphs
• On Sufficient Degree Conditions for a Graph to be $k$-linked
• A simpler proof of the excluded minor theorem for higher surfaces
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• Separating cycles in doubly toroidal embeddings
• Graphs with forbidden subgraphs
• Beweis einer Abschwächung der Hadwiger-Vermutung
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Graph Drawing
• On the structure of 5- and 6-chromatic abstract graphs.
• Complete minors in \(K_{s,s}\)-free graphs
• Approximation algorithms via contraction decomposition
• Computing Vertex Connectivity: New Bounds from Old Techniques
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor
• Topological minors in graphs of large girth
• Combinatorial Local Planarity and the Width of Graph Embeddings
• A newly recognized intrinsically knotted graph
• Cliques in dense GF(\(q\))-representable matroids
• Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
• Graph minors. XIX: Well-quasi-ordering on a surface.
• \(K_{a,k}\) minors in graphs of bounded tree-width
• Fractional colouring and Hadwiger's conjecture
• A relaxed Hadwiger's conjecture for list colorings
• Efficient algorithms for acyclic colorings of graphs
• Coloring locally bipartite graphs on surfaces.
• Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
• Obstructions to branch-decomposition of matroids
• On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
• Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
• A counter-example to ‘Wagner's conjecture’ for infinite graphs
• Trennende Knotenpunktmengen und Reduzibilität abstrakter Graphen mit Anwendung auf das Vierfarbenproblem.
• Grids and their minors
• Excluding a countable clique
• The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs
• Disjoint cocircuits in matroids with large rank
• On the structure of \(k\)-connected graphs without \(K_{k}\)-minor
• Graph minors and graphs on surfaces
• Excluding Subdivisions of Infinite Cliques
• K-linked graphs with girth condition
• Graph minors and linkages
• Excluding infinite clique minors
• The extremal function for 3-linked graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph minors. X: Obstructions to tree-decomposition
• Applications of a Planar Separator Theorem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph minors. XX: Wagner's conjecture
• Typical subgraphs of 3- and 4-connected graphs
• The directed subgraph homeomorphism problem
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• The extremal function for unbalanced bipartite minors
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• On \(K_{s,t}\)-minors in graphs with given average degree. II
• The extremal function for complete minors
• Directed tree-width
• Graph minors. XIII: The disjoint paths problem
• The extremal function for noncomplete minors
• The extremal function for \(K_{9}\) minors
• Homomorphiesätze für Graphen
• Graphs on surfaces
• An extremal function for contractions of graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Approximation algorithms for NP-complete problems on planar graphs
• Contractions to k₈
• The Point-Arboricity of Planar Graphs
• Forcing unbalanced complete bipartite minors
• Lower bound of the Hadwiger number of graphs by their average degree
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Mangoes and blueberries
• Disjoint paths in graphs
• 2-linked graphs
• 103 graphs that are irreducible for the projective plane
• Highly connected sets and the excluded grid theorem
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Every planar graph is 5-choosable
• Quickly excluding a planar graph
• The four-colour theorem
• Color-critical graphs on a fixed surface
• Branch-width and Rota's conjecture
• Surfaces, tree-width, clique-minors, and partitions
• Petersen family minors
• Graph minors. II. Algorithmic aspects of tree-width
• A kuratowski theorem for the projective plane
• A Separator Theorem for Nonplanar Graphs
• Graph colorings with local constraints -- a survey
• On Independent Circuits Contained in a Graph
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• An improved linear edge bound for graph linkages
• A characterization of graphs with no cube minor
• An excluded minor theorem for the octahedron
• Topological cliques in graphs II
• An excluded minor theorem for the Octahedron plus an edge
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Graph minors. I. Excluding a forest
• Knots and links in spatial graphs
• On the Computational Complexity of Combinatorial Problems
• Note on the irreducible triangulations of the Klein bottle
• S-functions for graphs
• Multiplicities of eigenvalues and tree-width of graphs
• Graph minors. III. Planar tree-width
• Highly linked graphs
• Two Minor Problems
• Dense minors in graphs of large girth
• Graph minors. XXI. graphs with unique linkages
• Graph minors. VI. Disjoint paths across a disc
• Zero knowledge and the chromatic number
• Diameter and treewidth in minor-closed graph families
• Graph minors. IX: Disjoint crossed paths
• A Kuratowski theorem for nonorientable surfaces
• Generating internally four-connected graphs
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
• Elimination of local bridges
• Graph minors. XXII. Irrelevant vertices in linkage problems
• List colourings of planar graphs
• Graph minors XXIII. Nash-Williams' immersion conjecture
• On the excluded minors for the matroids of branch-width \(k\)
• The complexity of planar graph choosability
• Excluding infinite minors
• Graph minors. XVI: Excluding a non-planar graph
• Uniqueness and minimality of large face-width embeddings of graphs
• Disjoint \(K_{r}\)-minors in large graphs with given average degree
• On the null space of a Colin de Verdière matrix
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Acyclic colorings of planar graphs
• Tangles, tree-decompositions and grids in matroids
• Branch-width and well-quasi-ordering in matroids and graphs.
• On Rota's conjecture and excluded minors containing large projective geometries.
• Linear connectivity forces large complete bipartite minors
• Graph minors. VII: Disjoint paths on a surface

Cited In (17)

• Connectivity and choosability of graphs with no \(K_t\) minor
• Local Hadwiger's conjecture
• Neighborhood contraction in graphs
• Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor
• The descriptive complexity of subgraph isomorphism without numerics
• Forbidden minors: finding the finite few
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• Spectral radius of finite and infinite planar graphs and of graphs of bounded genus
• Minimal universal and dense minor closed classes
• Recent progress towards Hadwiger's conjecture
• New tools and results in graph minor structure theory
• The \(\mathbb{Z}_2\)-genus of Kuratowski minors
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• Excluding Kuratowski graphs and their duals from binary matroids
• On the pathwidth of hyperbolic 3-manifolds
• Parameters Tied to Treewidth
• Refined List Version of Hadwiger’s Conjecture

This page was built for publication: Some recent progress and applications in graph minor theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q878052)