Chromatic number of randomly augmented graphs by Prof. Anand Srivastav, Kiel University

Abstract: An extension of the Erdős-Renyi random graph model Gn,p is the model of perturbed graphs introduced by Bohman, Frieze and Martin (Bohman, Frieze,

Martin 2003). This is a special case of the randomly augmented graphs studied in this paper. An augmented graph is the union of a deterministic host graph

and a random graph. Among the first problems in perturbed graphs has been the question how many random edges are needed to ensure Hamiltonicity of

the graph. This question was answered in the paper by Bohman, Frieze and Martin. The host graph is often chosen to be a dense graph. In recent years

several papers on combinatorial functions of perturbed graphs were published, e.g. on the emergence of powers of Hamiltonian cycles (Dudek, Reiher, Ruciński,

Schacht 2020), the properties of Positional Games played on perturbed graphs (Clemens, Hamann, Mogge, Parczyk, 2020) and the emergence of multiple

invariants e.g. fixed clique size (Bohman, Frieze, Krivelevich, Martin, 2004). In this talk I will present our results on the chromatic number of randomly augmented

graphs.