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 (only showing first 100 items - show all)

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

This page was built for publication: The extremal function for complete minors