An extremal function for contractions of graphs
From MaRDI portal
Publication:3344229
DOI10.1017/S0305004100061521zbMATH Open0551.05047WikidataQ56235115 ScholiaQ56235115MaRDI QIDQ3344229FDOQ3344229
Authors: Andrew Thomason 
Publication date: 1984
Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Combinatorial probability (60C05)
Cites Work
Cited In (only showing first 100 items - show all)
- Average degree conditions forcing a minor
- Forcing a sparse minor
- Minors in graphs of large girth
- On nowhere dense graphs
- The edge-density for \(K_{2,t}\) minors
- Forcing unbalanced complete bipartite minors
- Dense graphs have \(K_{3,t}\) minors
- The degree-diameter problem for sparse graph classes
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Colouring planar graphs with three colours and no large monochromatic components
- On the Hadwiger's conjecture for graph products
- On \(K_{s,t}\)-minors in graphs with given average degree
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Linear connectivity forces large complete bipartite minors
- Contractibility and the Hadwiger conjecture
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Colouring graphs with bounded generalized colouring number
- A relaxed Hadwiger's conjecture for list colorings
- Polynomial treewidth forces a large grid-like-minor
- Some remarks on the odd Hadwiger's conjecture
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- The extremal function for unbalanced bipartite minors
- Hadwiger number and the Cartesian product of graphs
- Graphs without minor complete subgraphs
- On the extremal function for graph minors
- On \(K_{s,t}\)-minors in graphs with given average degree. II
- The extremal function for complete minors
- Fractional colouring and Hadwiger's conjecture
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Cliques in graphs excluding a complete graph minor
- Small complete minors above the extremal edge density
- The extremal function for 3-linked graphs
- Surfaces, tree-width, clique-minors, and partitions
- Rank-width and tree-width of \(H\)-minor-free graphs
- Small minors in dense graphs
- The saga of minimum spanning trees
- Logarithmically small minors and topological minors
- Some recent progress and applications in graph minor theory
- Coloring immersion-free graphs
- Short proofs of some extremal results. II.
- The extremal function for Petersen minors
- An improved linear edge bound for graph linkages
- Strong complete minors in digraphs
- On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
- Grad and classes with bounded expansion. I: Decompositions
- Sublinear separators, fragility and subexponential expansion
- The extremal function for \(K_{9}\) minors
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Metric uniformization and spectral bounds for graphs
- On the maximum number of cliques in a graph
- Circumference and pathwidth of highly connected graphs
- On the structure of \(k\)-connected graphs without \(K_{k}\)-minor
- Hadwiger's conjecture
- On the odd-minor variant of Hadwiger's conjecture
- Fractional coloring and the odd Hadwiger's conjecture
- Structure and recognition of graphs with no 6-wheel subdivision
- Ramsey numbers of cubes versus cliques
- Clique minors in graphs and their complements
- High-girth graphs avoiding a minor are nearly bipartite
- Hat Guessing Numbers of Strongly Degenerate Graphs
- Number of cliques in graphs with a forbidden subdivision
- Boxicity of graphs on surfaces
- Girth and treewidth
- Every minor-closed property of sparse graphs is testable
- Asymptotic density of graphs excluding disconnected minors
- Packing and covering balls in graphs excluding a minor
- Note on coloring graphs without odd-\(K_k\)-minors
- On the number of cliques in graphs with a forbidden minor
- Minors in graphs of large \(\theta_r\)-girth
- List-coloring graphs without subdivisions and without immersions
- Boxicity, poset dimension, and excluded minors
- Proper minor-closed families are small
- Highly linked graphs
- Disjoint \(K_{r}\)-minors in large graphs with given average degree
- Property testing of massively parametrized problems -- a survey
- Improved bound for improper colourings of graphs with no odd clique minor
- Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
- Separators in region intersection graphs
- Connectivity and choosability of graphs with no \(K_t\) minor
- Immersion and clustered coloring
- The extremal function and Colin de Verdière graph parameter
- A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor
- The extremal function for disconnected minors
- Title not available (Why is that?)
- On a relationship between Hadwiger and stability numbers
- Extremal density for sparse minors and subdivisions
- On a recolouring version of Hadwiger's conjecture
- Allowing each node to communicate only once in a distributed system: shared whiteboard models
- Product structure of graph classes with bounded treewidth
- Partial result on Hadwiger's conjecture
- Local Hadwiger's conjecture
- Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- Some remarks on even-hole-free graphs
- Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant
- Large immersions in graphs with independence number 3 and 4
- Isomorphism Testing for Graphs Excluding Small Minors
- Complete directed minors and chromatic number
- Extremal functions for sparse minors
- Approximating the maximum clique minor and some subgraph homeomorphism problems
This page was built for publication: An extremal function for contractions of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3344229)
