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