Linear connectivity forces large complete bipartite minors
type: Item
instance of: scholarly article
title: Linear connectivity forces large complete bipartite minors
zbMATH Open document ID: 1214.05061
author: T. Böhme
author: Ken-ichi Kawarabayashi
author: John Maharry
author: Bojan Mohar
published in: Journal of Combinatorial Theory. Series B
publication date: 2009-06-23T00:00:00Z
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C83
zbMATH DE Number: 5569112
zbMATH Keywords: graph minor
zbMATH Keywords: tree-width
zbMATH Keywords: tree-decomposition
zbMATH Keywords: path-decomposition
zbMATH Keywords: complete graph minor
zbMATH Keywords: complete bipartite minor
zbMATH Keywords: unavoidable minor
zbMATH Keywords: connectivity
zbMATH Keywords: \(k\)-linked
zbMATH Keywords: Hadwiger conjecture
zbMATH Keywords: grid minor
zbMATH Keywords: vortex structure
zbMATH Keywords: near embedding
zbMATH Keywords: graphs on surfaces
zbMATH Keywords: Euler's formula
zbMATH Keywords: Erdős-Pósa property
MaRDI profile type: Publication
full work available at URL: j.jctb.2008.07.006
OpenAlex ID: W2166232733
cites work: Every planar map is four colorable. I: Discharging
cites work: Every planar map is four colorable. II: Reducibility
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Disjoint \(K_{r}\)-minors in large graphs with given average degree
cites work: \(K_{a,k}\) minors in graphs of bounded tree-width
cites work: Highly linked graphs
cites work: Q3999150
cites work: Q4947393
cites work: Highly connected sets and the excluded grid theorem
cites work: On the excluded minor structure theorem for graphs of large tree-width
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: Trennende Knotenpunktmengen und Reduzibilität abstrakter Graphen mit Anwendung auf das Vierfarbenproblem.
cites work: On the structure of 5- and 6-chromatic abstract graphs.
cites work: Q5342984
cites work: Q5759552
cites work: Q5837979
cites work: S-functions for graphs
cites work: Generating internally four-connected graphs
cites work: Contractions to k8
cites work: Elimination of local bridges
cites work: On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
cites work: Minors in large almost-5-connected non-planar graphs
cites work: On Sufficient Degree Conditions for a Graph to be $k$-linked
cites work: Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
cites work: A relaxed Hadwiger's conjecture for list colorings
cites work: Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
cites work: Q3333070
cites work: Lower bound of the Hadwiger number of graphs by their average degree
cites work: On \(K_{s,t}\)-minors in graphs with given average degree
cites work: Forcing unbalanced complete bipartite minors
cites work: Homomorphiesätze für Graphen
cites work: Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
cites work: An excluded minor theorem for the octahedron
cites work: A characterization of graphs with no cube minor
cites work: Graph minors and graphs on surfaces
cites work: Graphs on surfaces
cites work: The extremal function for unbalanced bipartite minors
cites work: The extremal function for noncomplete minors
cites work: Typical subgraphs of 3- and 4-connected graphs
cites work: Q4352948
cites work: Mangoes and blueberries
cites work: Fractional colouring and Hadwiger's conjecture
cites work: The four-colour theorem
cites work: Graph minors. III. Planar tree-width
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Q4273877
cites work: Graph minors. XIII: The disjoint paths problem

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Graph minors. XV: Giant steps

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Graph minors. XVII: Taming a vortex

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Graph minors. XVI: Excluding a non-planar graph

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Hadwiger's conjecture for \(K_ 6\)-free graphs

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Quickly excluding a planar graph

Linear connectivity forces large complete bipartite minors (cites work)
cites work: The extremal function for \(K_{9}\) minors

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Q4263662

Linear connectivity forces large complete bipartite minors (cites work)
cites work: An improved linear edge bound for graph linkages

Linear connectivity forces large complete bipartite minors (cites work)
cites work: An extremal function for contractions of graphs

Linear connectivity forces large complete bipartite minors (cites work)
cites work: The extremal function for complete minors

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Two Minor Problems

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Color-critical graphs on a fixed surface

Linear connectivity forces large complete bipartite minors (cites work)
cites work: Beweis einer Abschwächung der Hadwiger-Vermutung

Linear connectivity forces large complete bipartite minors (DOI)
DOI: 10.1016/J.JCTB.2008.07.006

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: Linear connectivity forces large complete bipartite minors: an alternative approach
Similarity Score: 0.9795847
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: Linear connectivity forces large complete bipartite minors: [J. Combin. Theory ser. B vol. 99, issue 2]
Similarity Score: 0.9435118
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: Path connectivity of line graphs and total graphs of complete bipartite graphs
Similarity Score: 0.873451
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: The generalized connectivity of the line graph and the total graph for the complete bipartite graph
Similarity Score: 0.8710669
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: Connectivity of large bipartite digraphs and graphs
Similarity Score: 0.8703816
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: Q5133269
Similarity Score: 0.8638668
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: Q5133103
Similarity Score: 0.8638668
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: Connectivity, graph minors, and subgraph multiplicity
Similarity Score: 0.85745823
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: Q4576317
Similarity Score: 0.85583705
Recommender Run: Recommender Run 3

Linear connectivity forces large complete bipartite minors (Recommended article)
Recommended article: On extremal bipartite graphs with a given connectivity
Similarity Score: 0.85576713
Recommender Run: Recommender Run 3