Cliques, chromatic number, and independent sets in the semi-random process

DOI10.1137/23M1561105zbMATH Open1546.05101MaRDI QIDQ6594390

David Gamarnik, Paweł Prałat, Mihyun Kang

Publication date: 28 August 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

cliquesindependent setssemi-random process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Title not available (Why is that?)
• Maximum matchings in a class of random graphs
• Differential equations for random processes and random graphs
• Corrigendum to: ``Existence of a perfect matching in a random \((1+e^{-1})\)-out bipartite graph
• Hamilton cycles in the semi-random graph process
• A gentle introduction to the differential equation method and dynamic concentration
• The probabilistic method
• Introduction to Random Graphs
• Hamilton cycles in 3-out
• Balls and bins: A study in negative dependence
• Semi‐random graph process
• Very fast construction of bounded-degree spanning graphs via the semi-random graph process
• Solutions of ordinary differential equations as limits of pure jump markov processes
• Perfect Matchings in the Semirandom Graph Process
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Power of \(k\) choices in the semi-random graph process
• Sharp thresholds in adaptive random graph processes
• A fully adaptive strategy for Hamiltonian cycles in the semi-random graph process
• Semi-random process without replacement

This page was built for publication: Cliques, chromatic number, and independent sets in the semi-random process

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