Phase transition of degeneracy in minor-closed families

DOI10.1016/J.AAM.2023.102489MaRDI QIDQ2689167zbMATH OpenOpenAlexFDO

Authors 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

degeneracygraph coloringgraph minorsphase transitionrandom subgraphs

Mathematics Subject Classification ID

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

Recommendations

• Chromatic thresholds in dense random graphs
• Maximum degree in minor-closed classes of graphs
• The chromatic thresholds of graphs
• Chromatic thresholds in sparse random graphs
• Breaking the degeneracy barrier for coloring graphs with no K_t minor

Cites work

• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• A lower bound on the average degree forcing a minor
• An extremal function for contractions of graphs
• Cliques in graphs excluding a complete graph minor
• Corrigendum: ``Forcing a sparse minor
• Dirac's map-color theorem for choosability
• Every monotone graph property has a sharp threshold
• Every planar graph is 5-choosable
• Extremal density for sparse minors and subdivisions
• Extremal functions for graph minors
• Extremal functions for sparse minors
• Forcing a sparse minor
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Homomorphiesätze für Graphen
• Homomorphism theorems for graphs
• scientific article; zbMATH DE number 3173143 (Why is no real title available?)
• scientific article; zbMATH DE number 3906521 (Why is no real title available?)
• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• scientific article; zbMATH DE number 475582 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Introduction to Random Graphs
• Local max-cut in smoothed polynomial time
• On percolation and \(\mathcal{NP}\)-hardness
• On the extremal function for graph minors
• On the number of cliques in graphs with a forbidden minor
• Percolation on finite graphs and isoperimetric inequalities.
• Random subgraphs of finite graphs. III: The phase transition for the n-cube
• Sachs' linkless embedding conjecture
• Sharp thresholds of graph properties, and the k-sat problem
• Size and connectivity of the \(k\)-core of a random graph
• Smoothed analysis of algorithms
• Smoothed analysis of local search for the maximum-cut problem
• Some simplified NP-complete graph problems
• Sudden emergence of a giant k-core in a random graph
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• The complexity of planar graph choosability
• The threshold probability for long cycles
• Threshold functions

Cited in

(1)

• Phase Transition of Degeneracy in Minor-Closed Families

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2689167)