Rooted K₄-minors

MaRDI QIDQ396793zbMATH OpenFDO

Authors David R. Wood, R. Fabila-Monroy

Publication date 14 August 2014

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

Full work available at URL https://arxiv.org/abs/1102.3760, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p64

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

zbMATH Keywords

graph theorygraph minorlinkagerooted minor

Mathematics Subject Classification ID

Graph minors (05C83)

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.

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

Cites work

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

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)