Rooted minor problems in highly connected graphs
type: Item
instance of: scholarly article
title: Rooted minor problems in highly connected graphs
zbMATH Open document ID: 1051.05075
author: Ken-ichi Kawarabayashi
published in: Discrete Mathematics
publication date: 2004-11-18T00:00:00Z
review text: A graph is said to have a rooted complete bipartite minor \(K_{a,k}\) if for every \(k\) distinct vertices \(v_1,\dots,v_k\) there are disjoint connected subgraphs \(H_1,\dots, H_a, K_1,\dots, K_k\) such that each of the \(K_i\) contains \(v_i\) and is adjacent to all \(H_1,\dots,H_a\). The author derives connectivity conditions for the existence of rooted complete bipartite minors from some known and deep connectivity or average degree conditions for the existence of (non-rooted) complete bipartite minors. Among others it is proved that for every \(a\) there is a constant \(N(a)\) such that every \(25k\)-connected graph of order at least \(N(a)\) has a rooted complete bipartite minor \(K_{a,k}\).
reviewed by: Dieter Rautenbach
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 2116261
zbMATH Keywords: rooted minor
zbMATH Keywords: connectivity
MaRDI profile type: Publication
full work available at URL: j.disc.2004.07.007
OpenAlex ID: W2081145725
cites work: Linear connectivity forces large complete bipartite minors
cites work: Highly linked graphs
cites work: Q4947393
cites work: Vertex partitions of \(K_{4,4}\)-minor free graphs
cites work: Extremal results for rooted minor problems
cites work: Forcing unbalanced complete bipartite minors
cites work: Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
cites work: On \(K_{s,t}\)-minors in graphs with given average degree
cites work: The extremal function for noncomplete minors
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Graph minors. IX: Disjoint crossed paths
cites work: Hadwiger's conjecture for \(K_ 6\)-free graphs
cites work: An improved linear edge bound for graph linkages
DOI: 10.1016/J.DISC.2004.07.007
description: scientific article; zbMATH DE number 2116261