Geodesic
Rooted \(K_4\)-minors
Ruy Fabila-Monroy1 ; David R. Wood2
1Cinvestav
2Monash University
The electronic journal of combinatorics, Tome 20 (2013) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/3476
Classification : 05C83
Mots-clés : graph theory, graph minor, rooted minor, linkage

Ruy Fabila-Monroy  1   ; David R. Wood  2

1 Cinvestav
2 Monash University 
@article{10_37236_3476,
     author = {Ruy Fabila-Monroy and David R. Wood},
     title = {Rooted {\(K_4\)-minors}},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {2},
     doi = {10.37236/3476},
     zbl = {1295.05218},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3476/}
}
TY  - JOUR
AU  - Ruy Fabila-Monroy
AU  - David R. Wood
TI  - Rooted \(K_4\)-minors
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3476/
DO  - 10.37236/3476
ID  - 10_37236_3476
ER  - 
%0 Journal Article
%A Ruy Fabila-Monroy
%A David R. Wood
%T Rooted \(K_4\)-minors
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3476/
%R 10.37236/3476
%F 10_37236_3476
Ruy Fabila-Monroy; David R. Wood. Rooted \(K_4\)-minors. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/3476

Cité par Sources :