Rooted K₄-minors

zbMATH Open1295.05218arXiv1102.3760MaRDI QIDQ396793FDOQ396793

Authors: David R. Wood, R. Fabila-Monroy 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $a,b,c,d$ be four vertices in a graph $G$. A emph{$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.

Full work available at URL: https://arxiv.org/abs/1102.3760

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Extremal results for rooted minor problems
• Rooted minor problems in highly connected graphs
• Rooted topological minors on four vertices
• Extremal functions for rooted minors
• A characterization of \(K_{2,4}\)-minor-free graphs

zbMATH Keywords

graph theorygraph minorlinkagerooted minor

Mathematics Subject Classification ID

Graph minors (05C83)

Cites Work

• Graph minors. XIII: The disjoint paths problem
• New Ore-type conditions for \(H\)-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Disjoint paths in graphs
• 2-linked graphs
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• The disjoint paths problem in quadratic time
• On the existence of certain disjoint arcs in graphs
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• 2-Isomorphic Graphs
• Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Rooted minor problems in highly connected graphs
• Solving the 2-disjoint paths problem in nearly linear time
• On \(H\)-linked graphs
• Thomassen's choosability argument revisited
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• Extremal functions for rooted minors
• A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
• Extremal results for rooted minor problems
• On Minimum Degree Implying That a Graph is H‐Linked
• Optimization and Recognition for K 5-minor Free Graphs in Linear Time
• An extremal problem for H‐linked graphs
• Pan-\(H\)-linked graphs
• A simple solution to the two paths problem in planar graphs
• Minimum degree conditions for \(H\)-linked graphs

Cited In (8)

• Extremal results for rooted minor problems
• Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
• Rooted minor problems in highly connected graphs
• Four terminal planar Delta-Wye reducibility via rooted K_2,4 minors
• A characterization of \(K_{2,4}\)-minor-free graphs
• Unique Colorability and Clique Minors
• Properties of 8-contraction-critical graphs with no \(K_7\) minor
• Vertex partitions of \(K_{4,4}\)-minor free graphs

This page was built for publication: Rooted \(K_4\)-minors

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