Chromatic number of randomly augmented graphs Article Swipe

MAKE IMPACT

Jan Geest , Anand Srivastav · YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2406.14223

An extension of the Erdős-Renyi random graph model $G_{n,p}$ is the model of perturbed graphs introduced by Bohman, Frieze and Martin (Bohman, Frieze, Martin 2003). This is a special case of the model of randomly augmented graphs studied in this paper. An augmented graph denoted by $pert_{H,p}$ is the union of a deterministic host graph and a random graph $G_{n,p}$. 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 problems in perturbed graphs were published, e.g. on the emergence of powers of Hamiltonian cycles (Dudek, Reiher, Ruciński, Schacht 2020), some positional games played on perturbed graphs (Clemens, Hamann, Mogge, Parczyk, 2020) and the behavior of multiple invariants e.g. fixed clique size (Bohman, Frieze, Krivelevich, Martin, 2004). In this paper we study the chromatic number of randomly augmented graphs. We concentrate on a host graph $H$ with chromatic number $o(n)$, augmented by a $G_{n,p}$ with $n^{-\frac{1}{3} + δ}\leq p(n) \leq 1-δ$ for some $δ\in (0,1)$. Our main result is an upper bound for the chromatic number: we show that asymptotically almost surely $χ(pert_{H,p}) \leq (1+o(1)) \cdot \frac{n \log(b)}{2 (\log(n) - \log(χ(H))}$ where $b = (1-p)^{-1}$. This result collapses to the famous theorem of Bollobás (1988), when $H$ is the empty host graph, thus our result can be regarded as a generalization of the latter. Our proof is not constructive. Further, we give a constructive coloring algorithm, when the chromatic number of the host graph is at most $\frac{n}{\log(n)^α},$ $α>\frac{1}{2}.$

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2406.14223

PDF

https://arxiv.org/pdf/2406.14223

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4399911626

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4399911626

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2406.14223

Digital Object Identifier

Title

Chromatic number of randomly augmented graphs

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2024

Year of publication

Publication date

2024-06-20

Full publication date if available

Authors

Jan Geest, Anand Srivastav

List of authors in order

Landing page

https://arxiv.org/abs/2406.14223

Publisher landing page

PDF URL

https://arxiv.org/pdf/2406.14223

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2406.14223

Direct OA link when available

Concepts

Chromatic scale, Mathematics, Combinatorics, Computer science

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload