Marcin Witkowski

activity

20112024

collaborators

Showing math.COShow all

5 papers · 1 filter

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…

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

Adjacency posets of outerplanar graphs

Counterexamples to Thomassen's conjecture on decomposition of cubic graphs

Hamilton Cycles in Random Lifts of Graphs

Nonrepetitive sequences on arithmetic progressions

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