On fractional fragility rates of graph classes

DOI10.37236/8909MaRDI QIDQ2205120zbMATH OpenOpenAlexFDO

Authors 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)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

nearly-matching lower boundsplanar graphprobability distribution

Mathematics Subject Classification ID

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

Abstract: We consider, for every positive integer $a$, probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from this distribution with probability at most $1/a$. Among other results, we prove that for every positive integer~$a$ and every planar graph $G$, there exists such a probability distribution with the additional property that deleting the random set creates a graph with component-size at most $(Delta(G)-1{)}^{a+O(sqrta)}$, or a graph with treedepth at most $O(a^{3}lo{g}_2(a))$. We also provide nearly-matching lower bounds.

Review text

Summary: We consider, for every positive integer \(a\), probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from this distribution with probability at most \(1/a\). Among other results, we prove that for every positive integer \(a\) and every planar graph \(G\), there exists such a probability distribution with the additional property that for any set \(X\) in the support of the distribution, the graph \(G-X\) has component-size at most \((\Delta(G)-1)^{a+O(\sqrt{a})}\), or treedepth at most \(O(a^3\log_2(a))\). We also provide nearly-matching lower bounds.

Recommendations

• Some Results on Fractional Graph Theory
• A note on fragile graphs
• Fractional factors and isolated toughness of graphs
• On fractional \((f,n)\)-critical graphs
• On toughness and fractional (g,f,n)-critical graphs
• On fractional K‐factors of random graphs
• scientific article; zbMATH DE number 1043893
• New toughness conditions for the fractional critical graphs
• On the fractional metric dimension of graphs
• On fractional metric dimension of graphs

Cites work

• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Colouring planar graphs with three colours and no large monochromatic components
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Diameter and treewidth in minor-closed graph families
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• Planar graphs have bounded queue-number
• Sparsity. Graphs, structures, and algorithms
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Sublinear separators, fragility and subexponential expansion

Cited in

(9)

• A note on fragile graphs
• Fundamentals of fractional revival in graphs
• Improved bounds for weak coloring numbers
• Planarization and fragmentability of some classes of graphs
• scientific article; zbMATH DE number 7446517 (Why is no real title available?)
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• PTAS for Sparse General-valued CSPs
• Colouring strong products
• Pliability and approximating Max-CSPs

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

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