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,*
(arXiv:1512.07849) (link) (in press)

**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

**Recognizing Graphs Close to Bipartite Graphs,**

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

*Leibniz International Proceedings in Informatics (LIPIcs),* 83 (2017) pp. 70:1--70:14
(Proceedings of MFCS 2017) (to appear)

**Clique-Width for Graph Classes Closed under Complementation,**

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

*Leibniz International Proceedings in Informatics (LIPIcs),* 83 (2017) pp. 73:1--73:14
(Proceedings of MFCS 2017) (arXiv:1705.07681) (to appear)

**Contracting Bipartite Graphs to Paths and Cycles**

K.K. Dabrowski and D. Paulusma,

*Electronic Notes in Discrete Mathematics,*
(Proceedings of Eurocomb 2017)
(arXiv:1706.03750)
(to appear)

**Clique-width and Well-Quasi Ordering of Triangle-Free Graph Classes**

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

*Lecture Notes in Computer Science,*
(Proceedings of WG 2017) (to appear)

**On the (parameterized) complexity of recognizing well-covered (r,l)-graphs,**

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

*Lecture Notes in Computer Science,* 10043 (2016) pp. 423-437
(Proceedings of COCOA 2016)
(arXiv:1705.09177)
(link)

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

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

*Lecture Notes in Computer Science,* 9843 (2016) pp. 253-265
(Proceedings
of IWOCA 2016)
(arXiv:1611.03671)
(link)

**Colouring Diamond-free Graphs,**

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

*Leibniz International Proceedings in Informatics (LIPIcs),* 53 (2016) pp. 16:1-16:14
(Proceedings of SWAT 2016)
(arXiv:1512.07849) (link)

**Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs,**

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

*Lecture Notes in Computer Science,* 9538 (2016) pp. 100-111
(Proceedings
of IWOCA 2015)
(arXiv:1506.06564)
(link)

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

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

*Electronic Notes in Discrete Mathematics,* 49 (2015) pp. 497-503
(Proceedings of EuroComb 2015)
(arXiv:1509.04273)
(link)

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

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

*Lecture Notes in Computer Science,* 9235 (2015) pp. 139-150
(Proceedings of MFCS 2015, Part II) (arXiv:1502.06948) (link)

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

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

*Lecture Notes in Computer Science,* 9139 (2015) pp. 143-156
(Proceedings of CSR 2015)
(arXiv:1508.02773)
(link)

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

K.K. Dabrowski and D. Paulusma,

*Lecture Notes in Computer Science,* 9079 (2015) pp. 167-181
(Proceedings of CIAC 2015)
(arXiv:1405.7092) (link)

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

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

*Lecture Notes in Computer Science,* 8977 (2015) pp. 676-688
(Proceedings of LATA 2015) (arXiv:1406.6298) (link)

**Editing to Eulerian Graphs,**

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

*Leibniz International Proceedings in Informatics (LIPIcs),* 29 (2014) pp. 97-108
(Proceedings of FSTTCS 2014) (arXiv:1410.6863) (link)

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

K.K. Dabrowski and D. Paulusma,

*Lecture Notes in Computer Science,* 8591 (2014) pp. 489-500
(Proceedings of COCOON 2014) (arXiv:1402.7060) (link)

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

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

*Lecture Notes in Computer Science,* 8165 (2013) pp. 201-212
(Proceedings
of WG 2013) (preprint) (link)

** Parameterized Algorithms for the Independent
Set Problem in Some Hereditary Graph Classes,**

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

*Lecture Notes in Computer Science,* 6460 (2011) pp. 1-9
(Proceedings
of IWOCA 2010) (preprint)
(link)

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

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

*Lecture Notes in Computer Science,* 6410 (2010) pp. 184-195
(Proceedings of WG 2010) (preprint)
(link)

Publications in Preparation

**Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide,**

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

**Dynamic Edge-choosability**

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

Other

**Structural Solutions to Maximum Independent Set and Related Problems**

K.K. Dabrowski, *PhD Thesis* (preprint) (link)

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)

Links

Quotes from various people

Imre Leader
Appreciation Society (mirrored from here)