Dr. Konrad Kazimierz Dąbrowski

Email:
konrad.dabrowski at durham.ac.uk |

I am a research associate supervised by Prof. Daniel Paulusma and Dr Matthew Johnson, funded by Leverhume Trust grant RPG-2016-258 "Efficient Graph Colouring Algorithms via Input Restrictions".
I work
mostly on graph structure and graph algorithms in restricted graph classes (from both a
parameterized and non-parameterized point of view).

I completed my PhD
in 2012, supervised by Prof. Vadim Lozin.
After that, I worked for six months as a research associate supervised by Prof. Daniel Paulusma
and Dr.
George Mertzios, funded by EPSRC grant EP/G043434/1
"Algorithmic Aspects of Graph
Coloring".
I then worked for six months as a research associate supervised by Prof. M.
Demange, funded by ANR grant TODO ANR 09-EMER-010
"Time Versus Optimality in Discrete Optimization".
After that I worked as a research associate supervised by Prof. Daniel Paulusma and Prof. Iain Stewart, funded by EPSRC grant EP/K025090/1
"Detecting Induced Graph Patterns".

Academic Responsibilities

I teach the LSEPI (Legal, Social, Ethical and Professional Issues) sub-module, which forms part of the COMP2201 Group Project module.

I previously taught part of the Algorithms and Complexity sub-module of COMP2181 Theory of Computation and part of the Logic and Discrete Structures sub-module of COMP1021 Mathematics for Computer Science.

I organised the ACiD Research Seminars and the Computer Science Junior Seminars.

Journal Publications

**Contracting Bipartite Graphs to Paths and Cycles**

K.K. Dabrowski and D. Paulusma,

*Information Processing Letters,* 127 (2017), pp. 37-42
(arXiv:1706.03750)
(link)

**Colouring Diamond-free Graphs,**

K.K. Dabrowski, F. Dross,
and D. Paulusma,

*Journal of Computer and System Sciences,* 89 (2017), pp. 410-431
(arXiv:1512.07849) (link)

**Well-quasi-ordering versus clique-width: new results on bigenic classes,**

K.K. Dabrowski, V.V. Lozin
and D. Paulusma,

*Order,*
(arXiv:1611.03671)
(link) (in press)

**Editing to a Planar Graph of Given Degrees,**

K.K. Dabrowski, P.A. Golovach, P. van 't Hof, D. Paulusma and D.M. Thilikos,

*Journal of Computer and System Sciences,* Volume 85, (2017), pp. 168-182
(arXiv:1508.02773)
(link)

**Bounding the Clique-Width of H-free Chordal Graphs,**

A. Brandstädt, K.K. Dabrowski, S. Huang and D. Paulusma,

*Journal of Graph Theory,* Volume 86(1), (2017), pp. 42-77
(arXiv:1502.06948) (link)

**Bounding Clique-Width via Perfect Graphs,**

K.K. Dabrowski, S. Huang and D. Paulusma,

*Journal of Computer and System Sciences,*
(arXiv:1406.6298) (link) (in press)

**Bounding the Clique-Width of H-free Split Graphs,**

A. Brandstädt, K.K. Dabrowski, S. Huang and D. Paulusma,

*Discrete Applied Mathematics,* Volume 211, (2016), pp. 30-39
(arXiv:1509.04273)
(link)

**Combinatorics and algorithms for augmenting graphs,**

K.K. Dabrowski,
V.V. Lozin,
D. de Werra and
V. Zamaraev,

*Graphs and Combinatorics,* Volume 32(4), (2016), pp. 1339-1352
(arXiv:1410.8774) (link)

**Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs,**

K.K. Dabrowski and D. Paulusma,

*The Computer Journal,* Volume 59(5), (2016), pp. 650-666
(arXiv:1405.7092) (link)

**Editing to Eulerian Graphs,**

K.K. Dabrowski, P.A. Golovach, P. van 't Hof and D. Paulusma,

*Journal of Computer and System Sciences,* Volume 82(2), (2016), pp. 213-228
(arXiv:1410.6863) (link)

**Classifying the Clique-Width of H-Free Bipartite Graphs,**

K.K. Dabrowski and D. Paulusma,

*Discrete Applied Mathematics,* Volume 200, (2016), pp. 43-51
(arXiv:1402.7060) (link)

**Stable-Pi Partitions of Graphs,**

K.K. Dabrowski, V.V.
Lozin and J. Stacho,

*Discrete Applied Mathematics,* Volume 182, (2015), pp. 104-114 (preprint) (link)

**Colouring of Graphs with Ramsey-Type Forbidden Subgraphs,**

K.K. Dabrowski, P.A.
Golovach and D. Paulusma,

*Theoretical Computer Science,* Volume 522, (2014), pp. 34-43 (preprint) (link)

**New Results on Maximum Induced Matchings in Bipartite Graphs and
Beyond,**

K.K. Dabrowski, M.
Demange and V.V.
Lozin,

*Theoretical Computer Science,* Volume 478, (2013), pp. 33-40
(preprint)
(link)

**On factorial properties of chordal bipartite graphs,**

K.K. Dabrowski, V.V.
Lozin,
and V. Zamaraev,

*Discrete Mathematics,* Volume 312, (16) (2012), pp.
2457-2465 (preprint)
(link)

** Parameterized complexity of the weighted independent set problem
beyond graphs of bounded clique number,**

K.K. Dabrowski, V.V.
Lozin,
H. Müller and D.
Rautenbach,

*Journal of Discrete Algorithms,* 14 (2012) pp. 207-213 (preprint)
(link)

**Colouring vertices of triangle-free graphs without forests,**

K.K. Dabrowski, V.V.
Lozin,
R. Raman and B.
Ries,

*Discrete Mathematics,* 312 (7) (2012) pp. 1372-1385
(preprint)
(link)

Conference Publications

**Independent Feedback Vertex Set for P _{5}-free Graphs,**

M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma,

M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma,

A. Blanché, K.K. Dabrowski, M. Johnson, V.V. Lozin D. Paulusma and V. Zamaraev,

K.K. Dabrowski and D. Paulusma,

K.K. Dabrowski, V.V. Lozin and D. Paulusma,

S.R. Alves, K.K. Dabrowski, L. Faria, S. Klein, I. Sau and U. Dos Santos Souza

K.K. Dabrowski, V.V. Lozin and D. Paulusma,

K.K. Dabrowski, F. Dross, and D. Paulusma,

K.K. Dabrowski, F. Dross, M. Johnson and D. Paulusma,

A. Brandstädt, K.K. Dabrowski, S. Huang and D. Paulusma,

A. Brandstädt, K.K. Dabrowski, S. Huang and D. Paulusma,

K.K. Dabrowski, P.A. Golovach, P. van 't Hof, D. Paulusma and D.M. Thilikos,

K.K. Dabrowski and D. Paulusma,

K.K. Dabrowski, S. Huang and D. Paulusma,

K.K. Dabrowski, P.A. Golovach, P. van 't Hof and D. Paulusma,

K.K. Dabrowski and D. Paulusma,

K.K. Dabrowski, P.A. Golovach and D. Paulusma,

K.K. Dabrowski, V.V. Lozin, H. Müller and D. Rautenbach,

K.K. Dabrowski, V.V. Lozin, R. Raman and B. Ries,

Publications in Preparation

M. Bonamy, K.K. Dabrowski, C. Feghali, M. Johnson and D. Paulusma, (submitted) (arXiv:1707.09383)

A. Blanché, K.K. Dabrowski, M. Johnson and D. Paulusma, (submitted) (arXiv:1607.06757)

K.K. Dabrowski, in preparation (preprint available on request)

Other

K.K. Dabrowski,

Conferences Organized

- I am the main organizer of the 22nd Postgraduate Combinatorial Conference 2012.
- I helped to organize the DIMAP Workshop on Combinatorics and Graph Theory.

Conferences/Meetings Attended

- 16-18 April 2009, Cambridge: Beyond Part III (participant)
- 12-17 July 2009, Cambridge: LMS/EPSRC Short course in Probabilistic Combinatorics (student)
- 10 November 2009, Oxford: Joint DIMAP-Oxford seminar (participant)
- 14 December 2009, Warwick: Mike's Mini-workshop on Algorithms (participant)
- 17 March 2010, Oxford: One-Day Meeting in Combinatorics (participant)
- 25-27 March 2010, Cambridge: Young Researchers in Mathematics (speaker)
- 6-9 April 2010, Edinburgh: 26th British Colloquium in Theoretical Computer Science (speaker)
- 12-16 April 2010, Warwick: European Study Group in Industry (participant)
- 10-11 June 2010, London: LTCC course on Synchronisation (student)
- 28 June - 16 July 2010, Oxford: Lecture series on Structural Graph Theory (student)
- 7-9 July 2010, London (Queen Mary): 21st Postgraduate Combinatorics Conference (speaker)
- 12-16 July 2010, Warwick: DIMAP Summer School on Approximation and Randomized Algorithms (student)
- 26-28 July 2010, London (King's College): 21st International Workshop on Combinatorial Algorithms (speaker)
- 20-22 September 2010, Durham: Algorithms and Complexity in Durham 2010 (participant)
- 2 February 2011, Open University: Open University Winter Combinatorics Meeting (participant)
- 16 March 2011, Oxford: One-Day Meeting in Combinatorics (participant)
- 14-16 April 2011, Warwick: Young Researchers in Mathematics (speaker)
- 18-21 April 2011, Birmingham: 27th British Colloquium for Theoretical Computer Science (speaker)
- 4-8 July 2011, Exeter: 23rd British Combinatorial Conference (speaker)
- 4-9 September 2011, Nový Smokovec, High Tatras, Slovakia: Workshop Cycles and Colourings (speaker)
- 28 September 2011, Warwick: DIMAP Retreat (speaker)
- 25 January 2012, Open University: Open University Winter Combinatorics Meeting (participant)
- 2-4 April 2012, Bristol: Young Researchers in Mathematics (speaker)
- 30 May 2012, Oxford: One-Day Meeting in Combinatorics (participant)
- 8 July 2012, Warwick: Workshop on Applications of Parameterized Algorithms and Complexity (participant)
- 9-13 July 2012, Warwick: International Colloquium on Automata, Languages and Programming (participant)
- 5-7 September 2012, Oxford: French-British Workshop on Analytic Combinatorics (participant)
- 9-14 September 2012, Nový Smokovec, High Tatras, Slovakia 21st Workshop Cycles and Colourings (participant)
- 14-15 September 2012, Nový Smokovec, High Tatras, Slovakia Hereditarnia 2012, The 15th Workshop on Hereditary Graph Properties (speaker)
- 13 December 2012, Durham, ACiD Seminar (speaker)
- 30 January 2013, Open University: Open University Winter Combinatorics Meeting (participant)
- 30 May - 1 June 2013, Paris (CNAM): Conference of the European Chapter on Combinatorial Optimization (participant)
- 4 June 2013, Paris (LIAFA): Journées Franciliennes de Recherche Opérationnelle (participant)
- 19-21 June 2013, Lübeck: International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013) (speaker)
- 7 July 2013, Riga: International Workshop on Approximation, Parameterized and EXact algorithms (speaker)
- 8-12 July 2013, Riga: International Colloquium on Automata, Languages and Programming (participant)
- 5-9 August 2013, Saarbrücken: Advanced Course on the Foundations of Computer Science (participant)
- 9-14 September 2013, Nový Smokovec, High Tatras, Slovakia: 22nd Workshop Cycles and Colourings (speaker)
- 20 November 2013, Durham: Network Coding, Partitions and Security (participant)
- 23 June 2014, Durham: Computer Science Junior Seminar (speaker)
- 4-6 August 2014, Atlanta GA, USA: 20th International Computing and Combinatorics Conference (COCOON 2014) (speaker)
- 7-12 September 2014, Nový Smokovec, High Tatras, Slovakia: 23rd Workshop Cycles and Colourings (speaker)
- 13-14 December 2014, New Delhi, India: New Developments in Exact Algorithms and Lower Bounds (participant)
- 15-17 December 2014, New Delhi, India: 34th Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014) (speaker)
- 11 February 2015, Durham: Computer Science Junior Seminar (speaker)
- 2-6 March 2015, Nice, France: 9th International Conference on Language and Automata Theory and Applications (LATA 2015) (speaker)
- 20-22 May 2015, Paris, France: 9th International Conference on Algorithms and Complexity (CIAC 2015) (speaker)
- 16-19 June 2015, Koper, Slovenia: Algorithmic Graph Theory on the Adriatic Coast (AGTAC 2015) (speaker)
- 6-10 July 2015, Warwick, UK: 25th British Combinatorial Conference (BCC 2015) (speaker)
- 24-28 August 2015, Milan, Italy: 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015) (speaker)
- 31 August - 4 September 2015, Bergen, Norway: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015) (speaker*2)
- 8 October 2015, Durham: Durham University School of Engineering and Computing Science Research Day (speaker)
- 11-15 October 2015, Aussois, France: 7th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2015) (speaker)
- 22-24 June 2016, Reykjavik, Iceland: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) (speaker)
- 16 August 2016, Helsinki, Finland: StringMasters Workshop 2016 (participant)
- 17-19 August 2016, Helsinki, Finland: 27th International Workshop on Combinatorial Algorithms (IWOCA 2016) (speaker)
- 4-9 September 2016, Nový Smokovec, High Tatras, Slovakia: 25th Workshop Cycles and Colourings (speaker)
- 9-13 January 2017, Durham, UK: Algebraic, Topological and Complexity Aspects of Graph Covers (ATCAGC 2017) (participant)
- 7 February 2017, Warwick, UK: DIMAP research seminar (speaker)
- 21-23 June 2017, Eindhoven, The Netherlands: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science
- 26-30 June 2017, Nantes, France: Research visit (visitor)
- 28 August - 1 September 2017, Vienna, Austria: European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2017) (speaker)

Links

Quotes from various people

Imre Leader
Appreciation Society (mirrored from here)