Local resilience of graphs
From MaRDI portal
Publication:3608302
DOI10.1002/rsa.20235zbMath1182.05114arXiv0706.4104WikidataQ105583252 ScholiaQ105583252MaRDI QIDQ3608302
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
random graphs; chromatic number; extremal problems; pseudorandom graphs; hamiltonicity; graph resilience
05C80: Random graphs (graph-theoretic aspects)
05C15: Coloring of graphs and hypergraphs
05C45: Eulerian and Hamiltonian graphs
Related Items
Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers, Turánnical hypergraphs, Unnamed Item, Packing trees of unbounded degrees in random graphs, Long paths and cycles in random subgraphs of graphs with large minimum degree, 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), On the Stability of the Graph Independence Number, When Do Envy-Free Allocations Exist?, Tight Hamilton cycles in random hypergraphs, Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs, Robust Hamiltonicity of Dirac graphs, Resilience for the Littlewood-Offord problem, Resilience for the Littlewood-Offord problem, Graph Tilings in Incompatibility Systems, The global resilience of Hamiltonicity in \(G(n, p)\), Covering cycles in sparse graphs, Counting and packing Hamilton cycles in dense graphs and oriented graphs, A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs, Compatible Hamilton cycles in Dirac graphs, Bandwidth theorem for random graphs, On two Hamilton cycle problems in random graphs, The number of Hamiltonian decompositions of regular graphs, Sandwiching random graphs: universality between random graph models, Recent progress in combinatorial random matrix theory, On the global strong resilience of fault Hamiltonian graphs, Dirac-type theorems in random hypergraphs, A Dirac-type theorem for Berge cycles in random hypergraphs, Rainbow factors in hypergraphs, Hamiltonicity in random graphs is born resilient, Robust Hamiltonicity of random directed graphs, On resilience of connectivity in the evolution of random graphs, Recent advances on the Hamiltonian problem: survey III, Packing spanning graphs from separable families, On the Hamiltonicity of random bipartite graphs, Triangle resilience of the square of a Hamilton cycle in random graphs, The threshold bias of the clique-factor game, Random directed graphs are robustly Hamiltonian, Compatible Hamilton cycles in random graphs, Almost spanning subgraphs of random graphs after adversarial edge removal, Corrádi and Hajnal's Theorem for Sparse Random Graphs, Long cycles in subgraphs of (pseudo)random directed graphs, On the rank of higher inclusion matrices, Hamiltonicity thresholds in Achlioptas processes, Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs, Dirac's theorem for random graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Generating random graphs in biased Maker-Breaker games
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