Stefan Glock

activity

20142026

most citedOptimal path and cycle decompositions of dense quasirandom graphs

25 citations · 107 across the 24 of their papers we have counts for

collaborators

Showing 2021Show all

5 papers · 1 filter

math.CO2021

The $n$ -queens completion problem

Stefan Glock, David Munhá Correia, Benny Sudakov

An $n$ -queens configuration is a placement of $n$ mutually non-attacking queens on an $n \times n$ chessboard. The $n$ -queens completion problem, introduced by Nauck in 1850, is to…

math.CO2021

Short proofs for long induced paths

Nemanja Draganić, Stefan Glock, Michael Krivelevich

We present a modification of the Depth first search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the ind…

math.CO2021

The largest hole in sparse random graphs

Nemanja Draganić, Stefan Glock, Michael Krivelevich

We show that for any $d = d (n)$ with $d_{0} (ε) \leq d = o (n)$ , with high probability, the size of a largest induced cycle in the random graph $G (n, d / n)$ is $(2 \pm ε) \frac{n}{d} lo g d$ . T…

math.CO2021

New results for MaxCut in $H$ -free graphs

Stefan Glock, Oliver Janzer, Benny Sudakov

The MaxCut problem asks for the size $mc (G)$ of a largest cut in a graph $G$ . It is well known that $mc (G) \geq m /2$ for any $m$ -edge graph $G$ , and the difference ${\rm…

math.CO2021★ 1 cited

Note on induced paths in sparse random graphs

Stefan Glock

We show that for $d \geq d_{0} (ε)$ , with high probability, the random graph $G (n, d / n)$ contains an induced path of length $(3/2 - ε) \frac{n}{d} lo g d$ . This improves a result obtained in…

The n-queens completion problem

Short proofs for long induced paths

The largest hole in sparse random graphs

New results for MaxCut in H-free graphs

Note on induced paths in sparse random graphs

The $n$ -queens completion problem

New results for MaxCut in $H$ -free graphs