George Kontogeorgiou

activity

20202026

most citedExact upper bounds for the minimum sizes of strong and weak separating path systems of cliques

2 citations · 2 across the 10 of their papers we have counts for

collaborators

13 papers

math.CO2026

Monochromatic components in dense 2-edge-coloured balanced bipartite graphs

César Bispo, George Kontogeorgiou, Marcelo Lage +2

We prove that each $2$ -edge-coloured spanning subgraph $G$ of $K_{n, n}$ with $δ (G) \geq ⌊(2 n + 1) /3 ⌋$ can be covered by at most three monochromatic components. We provide…

math.GR2026

Quasirandomness and Uniform Twin-Width

George Kontogeorgiou, Bobby Miraftab

For every nontrivial finite group, we prove that its quasirandom degree gives a polynomial lower bound on its uniform twin-width, whereas its minimum faithful complex representatio…

math.GR2026

Accessibility and Twin-width

George Kontogeorgiou, Bobby Miraftab

We show that finite twin-width does not imply accessibility for finitely generated groups, which answers a question of Esperet. That is, we prove that there exists a finitely gener…

math.CO2026

Rainbow Separating Path Systems

Alexander Clifton, George Kontogeorgiou, S Taruni +1

We introduce a colorful version of separating path systems, in which two edges can only be separated from each other by two paths of distinct colors. We calculate the minimum sizes…

math.CO2025

Separating path systems for cubic graphs and for complete bipartite graphs

Cristina Fernandes, Carlos Hoppen, George Kontogeorgiou +2

A strongly separating path system in a graph $G$ is a collection $P$ of paths in $G$ such that, for every two edges $e$ and $f$ of $G$ , there is a paths in $P$ …

math.CO2025

Separating edges by linearly many subdivisions

George Kontogeorgiou, Matias Pavez-Signe, Maya Stein +2

We prove that for any two graphs $G$ and $H$ , the edges of $G$ can be strongly separated by a collection of linearly many subdivisions of $H$ and single edges. This confirms a conj…

math.CO2025

Antidirected trees in directed graphs

George Kontogeorgiou, Giovanne Santos, Maya Stein

The Komlós-Sárközy-Szemerédi (KSS) theorem establishes that a certain bound on the minimum degree of a graph guarantees it contains all bounded degree trees of the same order. Rece…

math.CO2024★ 2 cited

Exact upper bounds for the minimum sizes of strong and weak separating path systems of cliques

George Kontogeorgiou, Maya Stein

We prove an upper bound of $n + 9$ for the strong separation number of the complete graph $K_{n}$ , and an upper bound of $n + 1$ for its weak separation number. This improves on the prev…

math.CO2024

Towards a Stallings-type theorem for finite groups

Johannes Carmesin, George Kontogeorgiou, Jan Kurkofka +1

A recent development in graph-minor theory is to study local separators, vertex-sets that separate graphs locally but not necessarily globally. The local separators of a graph roug…

math.CO2023

A short proof of the existence of a minor-universal countable planar graph

George Kontogeorgiou

We produce a new, shorter construction of a minor-universal planar graph.

math.CO2022

(Random) Trees of Intermediate Uniform Growth

George Kontogeorgiou, Martin Winter

For every sufficiently well-behaved function $g : R_{\geq 0} \to R_{\geq 0}$ that grows at least linearly and at most exponentially we construct a tree $T$ of u…

math.GT2022

Discrete group actions on 3-manifolds and embeddable Cayley complexes

Agelos Georgakopoulos, George Kontogeorgiou

We prove that a group $Γ$ admits a discrete topological (equivalently, smooth) action on some simply-connected 3-manifold if and only if $Γ$ has a Cayley complex embeddable -- with…

math.CO2020

Haystack Hunting Hints and Locker Room Communication

Artur Czumaj, George Kontogeorgiou, Mike Paterson

We want to efficiently find a specific object in a large unstructured set, which we model by a random $n$ -permutation, and we have to do it by revealing just a single element. Clea…