Paweł Prałat

activity

20122026

collaborators

Showing math.COShow all

6 papers · 1 filter

math.CO2026

Triangle-Saturated Graphs in the Semi-Random Graph Process

Felix Christian Clemen, Pawel Pralat

The semi-random graph process is an adaptive random graph process in which an online algorithm is initially given an empty graph on $n$ vertices. In each round, a vertex $u$ is pre…

math.CO2026

Canonical labelling of random regular graphs

Mikhail Isaev, Tamás Makai, Brendan McKay +3

We prove that whenever $d = d (n) \to \infty$ and $n - d \to \infty$ as $n \to \infty$ , then with high probability for any non-trivial initial colouring, the colour refinement algorithm disti…

math.CO2025

Multiset Metric Dimension of Binomial Random Graphs

Austin Eide, Pawel Pralat

For a graph $G = (V, E)$ and a subset $R \subseteq V$ , we say that $R$ is \textit{multiset resolving} for $G$ if for every pair of vertices $v, w$ , the \textit{multisets} $\{d(v,r):…

math.CO2025

Playing Sudoku on random 3-regular graphs

Jack Dippel, Austin Eide, Pawel Pralat +1

The Sudoku number $s (G)$ of graph $G$ with chromatic number $χ (G)$ is the smallest partial $χ (G)$ -colouring of $G$ that determines a unique $χ (G)$ -colouring of the entire graph. We…

math.CO2024

Burning Random Trees

Luc Devroye, Austin Eide, Pawel Pralat

Let $T$ be a Galton-Watson tree with a given offspring distribution $ξ$ , where $ξ$ is a $Z_{\geq 0}$ -valued random variable with $E [ξ] = 1$ and $0 < σ^{2}:=Var[ξ] < \inft…

math.CO2012

Sparse graphs are not flammable

Paweł Prałat

In this paper, we consider the following \emph{ $k$ -many firefighter problem} on a finite graph $G = (V, E)$ . Suppose that a fire breaks out at a given vertex $v \in V$ . In each subseq…