Research

My research is primarily concerned with graph theory and combinatorics. I am especially interested in random graphs (random lifts of graphs), graph dimension (as a dimension of its incidence poset) and algorithms on graphs.
I am also interested in game theory, nonrepetitive words, probabilistic methods, and heuristics.

Curriculum vitae

I was a participant of the HCP Programme for Ph.D. students SSDNM.
Here You can find my CV.
List of conferences I attended.

Scopus

Papers

Nr Author/s Title Year Journal/Proceedings URL
23 A. Czygrinow
M. Hańękowiak
A. Rumiński
M. Witkowski
Distributed approximation for $f$-matching ? submitted
22 A. Choryński
P. Matczak
A. Jeran
M. Witkowski
Extreme weather events and small municipalities resilience in Wielkopolska Province 2023 International Journal of Disaster Risk Reduction, Volume 95, article id. 103928.
21 S.Felsner
R. Hämäläinen
H. Smith
M. Witkowski
On the Erdos-Szekeres Problem for Convex Permutations and Orthogonally Convex Point Sets In preparation
20 M. Witkowski Adjacency posets of intervals intersection graphs In preparation
19 A. Czygrinow
M. Hańękowiak
M. Witkowski
Distributed distance domination in graphs with no K_{2,t}-minor 2022 Theoretical Computer Science, 2022, vol. 19, pp.22-30
18 C. Dominic
£.Witkowski
M. Witkowski
Cop-Edge Critical Generalized Petersen and Payley graphs 2022 Communications in Combinatorics and Optimization, 2023, pp.1-20
17 A. Czygrinow
M. Hańękowiak
R. Steiner
F. Schröder
M.Witkowski
Proper orientations of k-degenerate graphs In preparation
16 M. Witkowski On the existence of low dimensional bipartite posets with no S_k containing high dimensional subposets In preparation
15 M. Witkowski Adjacency posets of outerplanar graphs 2021 Discrete Mathematics, Volume 344, Issue 5
14 T. Bellitto
T. Klimosova
M. Merker
M. Witkowski
Y Yuditsky
Counterexamples to Thomassen's conjecture on decomposition of cubic graphs 2021 Graphs and Combinatorics (2021): 1-5. Web. Graphs and Combinatorics.
13 A. Czygrinow
M. Hańękowiak
M. Witkowski
Distributed approximations of $f$-matchings and $b$-matchings in graphs of sub-logarithmic expansion 2021 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
12 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed algorithms for k-dominating set in bounded genus graphs and linklessly embeddable graphs -extended version 2020 Theoretical Computer Science Volume 809: 327-338 (2020)
11 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed CONGEST BC constant approximation of MDS problem in bounded genus graphs 2019 Theoretical Computer Science Volume 757,: 1-10 (2019)
10 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed approximation algorithms for the Minimum Dominating Set in K_h-minor-free graphs 2018 29th International Symposium on Algorithms and Computation (ISAAC 2018), (22) 1-22, Leibniz International Proceedings in Informatics (LIPIcs)
9 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed algorithms for k-dominating set in bounded genus graphs and linklessly embeddable graphs 2017 Italian Conference on Theoretical Computer Science 2017
8 D.M. Cardoso
C. Dominic
£. Witkowski
M. Witkowski
A short note on cops and robber playing on total graph 2017 Asian Journal of Mathematics and Computer Research 16 (1), (2017), pp. 2395-4205
7 A. Czygrinow
M. Hańękowiak
E. Szymańska
W. Wawrzyniak
M. Witkowski
Improved distributed local approximation algorithm of the minimum 2-dominating set in planar graphs. 2017 Theoretical Computer Science, Vol 662, (2017), pp.1-8
6 D.M. Cardoso
C. Dominic
£.Witkowski
M. Witkowski
On Cops and Robbers on G[-] and cop-edge critical graphs. 2017 Contributions to Discrete Mathematics, Volume 12, Number 2 (2017) pp.167-186
5 A. Czygrinow
M. Hańękowiak
E. Szymańska
W. Wawrzyniak
M. Witkowski
Distributed local approximation of the minimum k-tuple dominating set in planar graphs. 2014 Proceedings of the 18th International Conference on Principles of Distributed Systems, OPODIS 2014
4 T. £uczak
£. Witkowski
M. Witkowski
Hamilton cycles in random lifts of graphs 2015 European Journal of Combinatorics, Vol 49 (2015), pp. 105-116
3 M.Witkowski Random lifts of graphs are highly connected 2013 Electronic Journal of Combinatorics 20(2) (2013)
2 L.Epstein
M.Feldman
T.Tamir
£. Witkowski
M. Witkowski
Approximate Strong Equilibria in Job Scheduling Games: an Analysis for Two Uniformly Related Machines 2013 Discrete Applied Mathematics 161 (2013), pp. 1843-1858
1 J.Grytczuk
J.Kozik
M.Witkowski
Nonrepetitive sequences on arithmetic progressions 2011 Electronic Journal of Combinatorics 18(1) (2011)
T.£uczak
£.Witkowski
M.Witkowski
Hamilton cycles in random lifts of complete graphs 2010 Informal publication SSDNM page
£.Witkowski
M.Witkowski
Wp³yw liczebno¶ci grupy na jako¶ę kszta³cenia IV 2010 Informal note in Bulletin of Faculty of Mathematics and Computer Science

Presentations

Nr Author/s Title Year Conference URL
1 P. Matczak
M.Witkowski
Zastosowanie metody Qualitative Comparative Analysis z uæyciem zbiorów rozmytych do analizy porównawczej polityk przeciwpowodziowych w 6 krajach europejskich 2016 XVI Ogólnopolski Zjazd Socjologiczny 14-17 wrze¶nia 2016 Gdańsk

Co-authors

Thomas Belitto(1), Domingos Moreira Cardoso(2), Adam Choryński(1), Andrzej Czygrinow(8), Charles Dominic(3), Leah Epstein(1), Michal Feldman(1), Jaros³aw Grytczuk(1), Micha³ Hańękowiak(8), Tereza Klimo¹ovį(1), Agnieszka Jeran(1) Jakub Kozik(1), Tomasz £uczak(1), Piotr Matczak(1), Martin Merker(1), Andrzej Rumiński(1), Edyta Szymańska(2), Tami Tamir(1), Wojciech Wawrzyniak(6), £ukasz Witkowski(5), Yelena Yuditsky(1),

Conferences

I was co-organiser of the:
"Workshop on Structural Graph Theory", Gu³towy 2019
"Workshop on Structural Graph Theory", Gu³towy 2022

Grants

Random Lifts of Graphs, NCN Grant PRELUDIUM 2011/03/N/ST1/00426 - principal investigator (2011-2013).
Urban greenery mitigates urban heat island effects: A comparative study of Beijing and Warsaw, NCN grant for Polish-Chinese cooperation SHENG3 (2024-2026) - investigator urbeat.site