Marcin Brianski

activity

20202024

collaborators

3 papers

math.CO2024

Erdős-Pósa property of tripods in directed graphs

Marcin Briański, Meike Hatzel, Karolina Okrasa +1

Let $D$ be a directed graphs with distinguished sets of sources $S \subseteq V (D)$ and sinks $T \subseteq V (D)$ . A tripod in $D$ is a subgraph consisting of the union of two $S$ - $T$ -…

math.CO2021

Reconfiguring Independent Sets on Interval Graphs

Marcin Briański, Stefan Felsner, Jędrzej Hodor +1

We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size $k$ are reconfigurable in an $n$ -vertex i…

math.CO2020

Erdős-Hajnal properties for powers of sparse graphs

Marcin Briański, Piotr Micek, Michał Pilipczuk +1

We prove that for every nowhere dense class of graphs $C$ , positive integer $d$ , and $ε > 0$ , the following holds: in every $n$ -vertex graph $G$ from $\mathcal{C}…