Phase transition of degeneracy in minor-closed families

DOI10.1016/j.aam.2023.102489OpenAlexW4318952084MaRDI QIDQ2689167

Chun-Hung Liu, Fan Wei

Publication date: 9 March 2023

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.02375

zbMATH Keywords

phase transitiongraph coloringdegeneracygraph minorsrandom subgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cliques in graphs excluding a complete graph minor
• Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube
• Threshold functions
• The complexity of planar graph choosability
• Size and connectivity of the \(k\)-core of a random graph
• Some simplified NP-complete graph problems
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Every planar graph is 5-choosable
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• Percolation on finite graphs and isoperimetric inequalities.
• Sachs' linkless embedding conjecture
• Sudden emergence of a giant \(k\)-core in a random graph
• A lower bound on the average degree forcing a minor
• On the number of cliques in graphs with a forbidden minor
• Homomorphiesätze für Graphen
• Homomorphism theorems for graphs
• Introduction to Random Graphs
• An extremal function for contractions of graphs
• Smoothed analysis of algorithms
• Sharp thresholds of graph properties, and the $k$-sat problem
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• On percolation and ‐hardness
• Every monotone graph property has a sharp threshold
• Dirac's map-color theorem for choosability
• Smoothed Analysis of Local Search for the Maximum-Cut Problem
• Local max-cut in smoothed polynomial time
• Extremal density for sparse minors and subdivisions
• Forcing a sparse minor
• ‘Forcing a sparse minor’ — CORRIGENDUM
• The Threshold Probability for Long Cycles
• Extremal functions for sparse minors
• On the extremal function for graph minors

This page was built for publication: Phase transition of degeneracy in minor-closed families