On fractional fragility rates of graph classes

DOI10.37236/8909zbMath1471.60011arXiv1907.12634OpenAlexW3094053427MaRDI QIDQ2205120

Zdeněk Dvořák, Jean-Sébastien Sereni

Publication date: 20 October 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

probability distributionplanar graphnearly-matching lower bounds

Mathematics Subject Classification ID

Trees (05C05) Probability distributions: general theory (60E05) Combinatorial probability (60C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Improved bounds for weak coloring numbers ⋮ Clustered colouring of graph classes with bounded treedepth or pathwidth ⋮ PTAS for Sparse General-valued CSPs

Cites Work

• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Graph minors. III. Planar tree-width
• Sublinear separators, fragility and subexponential expansion
• Diameter and treewidth in minor-closed graph families
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Graph minors. II. Algorithmic aspects of tree-width
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Planar Graphs Have Bounded Queue-Number
• Colouring Planar Graphs With Three Colours and No Large Monochromatic Components

This page was built for publication: On fractional fragility rates of graph classes