Local resilience of graphs

DOI10.1002/rsa.20235zbMath1182.05114arXiv0706.4104OpenAlexW2953347513WikidataQ105583252 ScholiaQ105583252MaRDI QIDQ3608302

Van H. Vu, Benjamin Sudakov

Publication date: 4 March 2009

Published in: Random Structures and Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphschromatic numberextremal problemspseudorandom graphshamiltonicitygraph resilience

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45)

Related Items (51)

Corrádi and Hajnal's Theorem for Sparse Random Graphs ⋮ Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs ⋮ Dirac-type theorems in random hypergraphs ⋮ Dirac's theorem for random graphs ⋮ Long cycles in subgraphs of (pseudo)random directed graphs ⋮ Sandwiching random graphs: universality between random graph models ⋮ Packing spanning graphs from separable families ⋮ On the Hamiltonicity of random bipartite graphs ⋮ Generating random graphs in biased Maker-Breaker games ⋮ On the rank of higher inclusion matrices ⋮ Counting and packing Hamilton cycles in dense graphs and oriented graphs ⋮ Robust Hamiltonicity of random directed graphs ⋮ Triangle resilience of the square of a Hamilton cycle in random graphs ⋮ The threshold bias of the clique-factor game ⋮ On resilience of connectivity in the evolution of random graphs ⋮ The number of Hamiltonian decompositions of regular graphs ⋮ Graph Tilings in Incompatibility Systems ⋮ The global resilience of Hamiltonicity in \(G(n, p)\) ⋮ Fixing knockout tournaments with seeds ⋮ Covering cycles in sparse graphs ⋮ A Dirac-type theorem for Berge cycles in random hypergraphs ⋮ Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ When Do Envy-Free Allocations Exist? ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Turánnical hypergraphs ⋮ On two Hamilton cycle problems in random graphs ⋮ A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs ⋮ Compatible Hamilton cycles in Dirac graphs ⋮ Robust Hamiltonicity of Dirac graphs ⋮ Unnamed Item ⋮ Hamiltonicity thresholds in Achlioptas processes ⋮ Resilience for the Littlewood-Offord problem ⋮ Resilience for the Littlewood-Offord problem ⋮ Recent progress in combinatorial random matrix theory ⋮ Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs ⋮ Rainbow factors in hypergraphs ⋮ Packing trees of unbounded degrees in random graphs ⋮ Random directed graphs are robustly Hamiltonian ⋮ Long paths and cycles in random subgraphs of graphs with large minimum degree ⋮ Compatible Hamilton cycles in random graphs ⋮ Bandwidth theorem for random graphs ⋮ On the global strong resilience of fault Hamiltonian graphs ⋮ Almost spanning subgraphs of random graphs after adversarial edge removal ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ Dirac’s theorem for random regular graphs ⋮ Robustness of randomized rumour spreading ⋮ All Feedback Arc Sets of a Random Turán Tournament Have $\lfloor {n}/{k}\rfloor-{k}+1$ Disjoint ${k}$-Cliques (and This Is Tight) ⋮ Tight Hamilton cycles in random hypergraphs ⋮ Hamiltonicity in random graphs is born resilient ⋮ On the Stability of the Graph Independence Number

Cites Work

• Unnamed Item
• An algorithm for finding Hamilton paths and cycles in random graphs
• Hamiltonian circuits in random graphs
• Sandwiching random graphs: universality between random graph models
• Sparse pseudo‐random graphs are Hamiltonian
• On the asymmetry of random regular graphs and random graphs
• On the probability of independent sets in random graphs
• The chromatic number of random graphs
• The chromatic number of random graphs

This page was built for publication: Local resilience of graphs