Marcin Witkowski

activity

20112024

collaborators

6 papers

math.CO2024

Half-integral Erdős-Pósa property for non-null $S$ - $T$ paths

Vera Chekan, Colin Geniet, Meike Hatzel +4

For a group $Γ$ , a $Γ$ -labelled graph is an undirected graph $G$ where every orientation of an edge is assigned an element of $Γ$ so that opposite orientations of the same edge are…

cs.DS2022

Distributed distance domination in graphs with no $K_{2, t}$ -minor

Andrzej Czygrinow, Michał Hanćkowiak, Marcin Witkowski

We prove that a simple distributed algorithm finds a constant approximation of an optimal distance- $k$ dominating set in graphs with no $K_{2, t}$ -minor. The algorithm runs in a con…

math.CO2020

Adjacency posets of outerplanar graphs

Marcin Witkowski

Felsner, Li and Trotter showed that the dimension of the adjacency poset of an outerplanar graph is at most 5, and gave an example of an outerplanar graph whose adjacency poset has…

math.CO2019

Counterexamples to Thomassen's conjecture on decomposition of cubic graphs

Thomas Bellitto, Tereza Klimošová, Martin Merker +2

We construct an infinite family of counterexamples to Thomassen's conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red…

math.CO2013

Hamilton Cycles in Random Lifts of Graphs

Tomasz Łuczak, Łukasz Witkowski, Marcin Witkowski

For a graph $G$ the random $n$ -lift of $G$ is obtained by replacing each of its vertices by a set of $n$ vertices, and joining a pair of sets by a random matching whenever the corr…

math.CO2011

Nonrepetitive sequences on arithmetic progressions

Jarosław Grytczuk, Jakub Kozik, Marcin Witkowski

A sequence $S = s_{1} s_{2} .. ._{n}$ is \emph{nonrepetitive} if no two adjacent blocks of $S$ are identical. In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequenc…

Half-integral Erdős-Pósa property for non-null S-T paths