The extremal function for complete minors

DOI10.1006/jctb.2000.2013zbMath1024.05083OpenAlexW2151438396WikidataQ56235116 ScholiaQ56235116MaRDI QIDQ1850528

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/80a6a6420c4658705d6f7a48f7013c1adcf7dcd1

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83)

Related Items

Complete minors and average degree: A short proof, Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth, On the extremal function for graph minors, A decomposition method on solving the linear arboricity conjecture, Recent progress towards Hadwiger's conjecture, Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications, On the generalised colouring numbers of graphs that exclude a fixed minor, Large complete minors in random subgraphs, Dynamic coloring of graphs having no \(K_5\) minor, On the critical densities of minor-closed classes, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Disjoint complete minors and bipartite minors, Minors in graphs of large girth, Cliques in graphs excluding a complete graph minor, Cycles of Given Size in a Dense Graph, Small complete minors above the extremal edge density, Parameterized Complexity for Domination Problems on Degenerate Graphs, Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model, Short proofs of some extremal results. II., A Relative of Hadwiger's Conjecture, A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor, Complete Minors in Graphs Without Sparse Cuts, Counting Small Induced Subgraphs Satisfying Monotone Properties, Intrinsically knotted and 4-linked directed graphs, The extremal function for disconnected minors, On the number of cliques in graphs with a forbidden minor, Minors in graphs of large \(\theta_r\)-girth, Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait, Clique immersion in graphs without a fixed bipartite graph, Some recent progress and applications in graph minor theory, Graphs without minor complete subgraphs, On the signed chromatic number of some classes of graphs, Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets, A relaxed Hadwiger's conjecture for list colorings, Strong-diameter decompositions of minor free graphs, A minimum degree condition forcing complete graph immersion, The edge-density for \(K_{2,t}\) minors, A lower bound on the average degree forcing a minor, Diameter bounds for planar graphs, Grad and classes with bounded expansion. I: Decompositions, Small minors in dense graphs, The extremal function for unbalanced bipartite minors, Forcing a sparse minor, On the Fiedler value of large planar graphs, Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor, Rainbow Turán number of clique subdivisions, On the purity of minor-closed classes of graphs, Asymptotic density of graphs excluding disconnected minors, Unnamed Item, Polynomial treewidth forces a large grid-like-minor, The degree-diameter problem for sparse graph classes, Disjoint unions of complete minors, On \(K_{s,t}\)-minors in graphs with given average degree, Compact topological minors in graphs, Efficient enumeration of dominating sets for sparse graphs, On the planar split thickness of graphs, On the links of vertices in simplicial \(d\)-complexes embeddable in the Euclidean \(2d\)-space, Some remarks on the odd Hadwiger's conjecture, On the parameterized complexity of the edge monitoring problem, The extremal function for Petersen minors, Fractional coloring and the odd Hadwiger's conjecture, On complexities of minus domination, Ramsey numbers of cubes versus cliques, Every minor-closed property of sparse graphs is testable, The Colin de Verdière parameter, excluded minors, and the spectral radius, On \(K_{s,t}\)-minors in graphs with given average degree. II, Minimum fill-in of sparse graphs: kernelization and approximation, Logarithmically small minors and topological minors, Unnamed Item, Disjoint \(K_{r}\)-minors in large graphs with given average degree, On the structure of \(k\)-connected graphs without \(K_{k}\)-minor, Forcing unbalanced complete bipartite minors, The extremal function for \(K_{9}\) minors, Rank-width and tree-width of \(H\)-minor-free graphs, Dense graphs have \(K_{3,t}\) minors, Contractibility and the Hadwiger conjecture, Kernelization hardness of connectivity problems in \(d\)-degenerate graphs, Computing a tree having a small vertex cover, The parameterized complexity of editing graphs for bounded degeneracy, Extremal infinite graph theory, Unnamed Item, Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs, A local epsilon version of Reed's conjecture, A Weakening of the Odd Hadwiger's Conjecture, On the maximum number of cliques in a graph, Many disjoint dense subgraphs versus large \(k\)-connected subgraphs in large graphs with given edge density, Extended formulations, nonnegative factorizations, and randomized communication protocols, The Impact of Locality in the Broadcast Congested Clique Model, Improper colouring of graphs with no odd clique minor, A Structure Theorem for Strong Immersions, Hadwiger’s Conjecture, Linear connectivity forces large complete bipartite minors, Note on coloring graphs without odd-\(K_k\)-minors, List-coloring graphs without \(K_{4,k}\)-minors, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, The order of the largest complete minor in a random graph, Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor, Linear time algorithms for finding a dominating set of fixed size in degenerated graphs, Tractable minor-free generalization of planar zero-field Ising models, The minimum number of minimal codewords in an \([n, k\)-code and in graphic codes], Connectivity and choosability of graphs with no \(K_t\) minor, Extremal connectivity for topological cliques in bipartite graphs, On Complexities of Minus Domination, The densest matroids in minor-closed classes with exponential growth rate, Extremal functions for sparse minors, Allowing each node to communicate only once in a distributed system: shared whiteboard models, Average degree conditions forcing a minor

Cites Work