Rooted minor problems in highly connected graphs

DOI10.1016/J.DISC.2004.07.007MaRDI QIDQ1886348zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi

Publication date 18 November 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2004.07.007

zbMATH Keywords

connectivityrooted minor

Mathematics Subject Classification ID

Connectivity (05C40) Graph minors (05C83)

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}\).

Recommendations

• Extremal results for rooted minor problems
• Extremal functions for rooted minors
• Disjoint complete minors and bipartite minors
• Linear connectivity forces large complete bipartite minors
• Rooted K₄-minors

Cites work

• An improved linear edge bound for graph linkages
• Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
• Extremal results for rooted minor problems
• Forcing unbalanced complete bipartite minors
• Graph minors. IX: Disjoint crossed paths
• Graph minors. XIII: The disjoint paths problem
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Highly linked graphs
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Linear connectivity forces large complete bipartite minors
• On \(K_{s,t}\)-minors in graphs with given average degree
• The extremal function for noncomplete minors
• Vertex partitions of \(K_{4,4}\)-minor free graphs

Cited in

(10)

• Note on coloring graphs without odd-\(K_k\)-minors
• List-coloring graphs without \(K_{4,k}\)-minors
• Extremal functions for rooted minors
• Rooted K₄-minors
• Linkless and flat embeddings in 3-space
• Forcing a K_r minor by high external connectivity
• Extremal results for rooted minor problems
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Chasing tripods to obtain a rooted subdivision
• A polynomial time algorithm for Steiner tree when terminals avoid a rooted K₄-minor

This page was built for publication: Rooted minor problems in highly connected graphs

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