Rooted \(K_4\)-minors
type: Item
instance of: scholarly article
title: Rooted \(K_4\)-minors
zbMATH Open document ID: 1295.05218
author: David R. Wood
author: R. Fabila-Monroy
published in: The Electronic Journal of Combinatorics
publication date: 2014-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1102.3760
full work available at URL: v20i2p64
review text: Summary: Let \(a,b,c,d\) be four vertices in a graph \(G\). A \(K_4\) minor rooted at \(a,b,c,d\) consists of four pairwise-disjoint pairwise-adjacent connected subgraphs of \(G\), respectively containing \(a,b,c,d\). We characterise precisely when \(G\) contains a \(K_4\)-minor rooted at \(a,b,c,d\) by describing six classes of obstructions, which are the edge-maximal graphs containing no \(K_4\)-minor rooted at \(a,b,c,d\). The following two special cases illustrate the full characterisation: (1) A 4-connected non-planar graph contains a \(K_4\)-minor rooted at \(a,b,c,d\) for every choice of \(a,b,c,d\). (2) A 3-connected planar graph contains a \(K_4\)-minor rooted at \(a,b,c,d\) if and only if \(a,b,c,d\) are not on a single face.
Mathematics Subject Classification ID: 05C83
zbMATH DE Number: 6330272
zbMATH Keywords: graph theory
zbMATH Keywords: graph minor
zbMATH Keywords: rooted minor
zbMATH Keywords: linkage
MaRDI profile type: Publication
arXiv ID: 1102.3760
cites work: In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
cites work: New Ore-type conditions for \(H\)-linked graphs
cites work: On \(H\)-linked graphs
cites work: Pan-\(H\)-linked graphs
cites work: On Minimum Degree Implying That a Graph is H‐Linked
cites work: A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
cites work: The disjoint paths problem in quadratic time
cites work: Extremal results for rooted minor problems
cites work: Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
cites work: Rooted minor problems in highly connected graphs
cites work: An extremal problem for H‐linked graphs
cites work: Minimum degree conditions for \(H\)-linked graphs
cites work: Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
cites work: Optimization and Recognition for K 5-minor Free Graphs in Linear Time
cites work: Graph minors XXIII. Nash-Williams' immersion conjecture
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Hadwiger's conjecture for \(K_ 6\)-free graphs
cites work: Disjoint paths in graphs
cites work: A Polynomial Solution to the Undirected Two Paths Problem
cites work: Solving the 2-disjoint paths problem in nearly linear time
cites work: 2-linked graphs
cites work: On the existence of certain disjoint arcs in graphs
cites work: 2-Isomorphic Graphs
cites work: A simple solution to the two paths problem in planar graphs
cites work: Extremal functions for rooted minors
cites work: Thomassen's Choosability Argument Revisited
description: scientific article; zbMATH DE number 6330272