Linear connectivity forces large complete bipartite minors
From MaRDI portal
Publication:1026000
DOI10.1016/j.jctb.2008.07.006zbMath1214.05061MaRDI QIDQ1026000
Ken-ichi Kawarabayashi, Bojan Mohar, Thomas Böhme, John Maharry
Publication date: 23 June 2009
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2008.07.006
connectivity; graph minor; vortex structure; path-decomposition; Euler's formula; Hadwiger conjecture; Erdős-Pósa property; tree-width; tree-decomposition; graphs on surfaces; unavoidable minor; complete bipartite minor; grid minor; near embedding; \(k\)-linked; complete graph minor
Related Items
The $\mathbb{Z}_2$-genus of Kuratowski minors, Extremal results for rooted minor problems, Unnamed Item, The Erdős-Pósa property for clique minors in highly connected graphs, Linear connectivity forces large complete bipartite minors: an alternative approach, Contractibility and the Hadwiger conjecture, On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture, Some recent progress and applications in graph minor theory, A relaxed Hadwiger's conjecture for list colorings, Some remarks on the odd Hadwiger's conjecture, Many disjoint dense subgraphs versus large \(k\)-connected subgraphs in large graphs with given edge density, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Note on coloring graphs without odd-\(K_k\)-minors, List-coloring graphs without \(K_{4,k}\)-minors, Rooted minor problems in highly connected graphs, On the excluded minor structure theorem for graphs of large tree-width, The \(\mathbb{Z}_2\)-genus of Kuratowski minors, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Disjoint complete minors and bipartite minors, Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets, A note on the saturation number of the family of \(k\)-connected graphs, The extremal function for \(K_{9}\) minors, Non-zero disjoint cycles in highly connected group labelled graphs, Extremal connectivity for topological cliques in bipartite graphs, Hadwiger’s Conjecture, Minors in large almost-5-connected non-planar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Forcing unbalanced complete bipartite minors
- Lower bound of the Hadwiger number of graphs by their average degree
- Graph minors. III. Planar tree-width
- Typical subgraphs of 3- and 4-connected graphs
- On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
- A relaxed Hadwiger's conjecture for list colorings
- On \(K_{s,t}\)-minors in graphs with given average degree
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Mangoes and blueberries
- Graph minors. X: Obstructions to tree-decomposition
- S-functions for graphs
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Highly connected sets and the excluded grid theorem
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Quickly excluding a planar graph
- The four-colour theorem
- Color-critical graphs on a fixed surface
- The extremal function for unbalanced bipartite minors
- Graph minors. XVI: Excluding a non-planar graph
- Fractional colouring and Hadwiger's conjecture
- Graph minors. XVII: Taming a vortex
- Disjoint \(K_{r}\)-minors in large graphs with given average degree
- An improved linear edge bound for graph linkages
- A characterization of graphs with no cube minor
- The extremal function for complete minors
- Generating internally four-connected graphs
- \(K_{a,k}\) minors in graphs of bounded tree-width
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XV: Giant steps
- On the excluded minor structure theorem for graphs of large tree-width
- The extremal function for noncomplete minors
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- The extremal function for \(K_{9}\) minors
- Homomorphiesätze für Graphen
- Beweis einer Abschwächung der Hadwiger-Vermutung
- Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
- Highly linked graphs
- Minors in large almost-5-connected non-planar graphs
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
- Trennende Knotenpunktmengen und Reduzibilität abstrakter Graphen mit Anwendung auf das Vierfarbenproblem.
- An extremal function for contractions of graphs
- On Sufficient Degree Conditions for a Graph to be $k$-linked
- An excluded minor theorem for the octahedron
- Contractions to k8
- Two Minor Problems
- On the structure of 5- and 6-chromatic abstract graphs.
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
