Publications
Conferences
Independent set reconfiguration in graphs without large bicliques, with Takehiro Ito and Hirotaka Ono, ISAAC 2014, Jeonju, Korea | preprint
The parameterized complexity of graph cyclability, with Petr Golovach, Spyridon Maniatis , and Dimitrios M. Thilikos, ESA 2014, Wrocław, Poland | preprint
Forbidden induced subgraphs and the price of connectivity for feedback vertex set, with Rémy Belmonte, Pim van ‘t Hof, and Daniël Paulusma, MFCS 2014, Budapest, Hungary | preprint
Reconfiguring independent sets in claw-free graphs, with Paul Bonsma and Marcin Wrochna, SWAT 2014, Copenhagen, Denmark | doi | preprint
On the parameterized complexity for token jumping on graphs, with Takehiro Ito, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka, TAMC 2014, Chennai, India | preprint
Chain minors are FPT, with Jarosław Błasiok, IPEC 2013, Sophia Antipolis, France | doi | preprint | slides
The price of connectivity for feedback vertex set, with Rémy Belmonte, Pim van ‘t Hof, and Daniël Paulusma, EuroComb 2013, Pisa, Italy | doi | preprint
Excluding graphs as immersions in surface embedded graphs, with Archontia C. Giannopoulou and Dimitrios M. Thilikos, WG 2013, Lübeck, Germany | preprint
Induced immersions, with Rémy Belmonte and Pim van ‘t Hof, ISAAC 2012, Taipei, Taiwan | doi | preprint
Characterizing graphs of small carving-width, with Rémy Belmonte, Pim van ‘t Hof, and Daniël Paulusma, and Dimitrios M. Thilikos, COCOA 2012, Banff, Canada | doi | preprint | slides (by Rémy)
Contraction checking in graphs on surfaces, with Dimitrios M. Thilikos, STACS 2012, Paris, France | doi (open access) | slides
Finding an induced path of given parity in planar graphs in polynomial time, with Naomi Nishimura, SODA 2012, Kyoto, Japan | doi | preprint | slides
Finding contractions and induced minors in chordal graphs via disjoint paths, with Rémy Belmonte, Petr Golovach, Pinar Heggernes, Pim van ‘t Hof, and Daniël Paulusma, ISAAC 2011, Yokohama, Japan | doi | preprint | slides (by Rémy)
Increasing the minimum degree by contractions, with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos, IPEC 2011, Saarbrücken, Germany | doi | preprint | slides (by Petr)
Lift contractions, with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos, EuroComb 2011, Budapest, Hungary | doi | preprint | slides (by Daniël)
Contracting a chordal graph to a split graph or a tree, with Petr Golovach and Daniël Paulusma, MFCS 2011, Warsaw, Poland | doi | preprint | slides
Shortest paths between shortest paths and independent sets, with Paul Medvedev and Martin Milanič, IWOCA 2010, London, UK | doi | preprint | slides (by Paul)
Max-Cut and containment relations in graphs, WG 2010, Zaros, Greece | doi | preprint | slides
Contractions of planar graphs in polynomial time, with Daniël Paulusma and Dimitrios M. Thilikos, ESA 2010, Liverpool, UK | doi | preprint | slides
Approximating maximum k-edge-colorable subgraphs, with Łukasz Kowalik, SWAT 2010, Bergen, Norway | doi | preprint | slides (by Łukasz)
The k-in-a-path problem for claw-free graphs, with Jiří Fiala, Bernard Lidický, and Daniël Paulusma, STACS 2010, Nancy, France | doi (open access) | slides
On contracting graphs to fixed pattern graphs, with Pim van ‘t Hof, Daniël Paulusma, Stefan Szeider, and Dimitrios M. Thilikos, SOFSEM 2010, Špindlerův Mlýn, Czech Republic | doi | preprint | slides (by Pim)
Induced packing of odd cycles in a planar graph, with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos, ISAAC 2009, Honolulu, USA | doi | preprint | slides
Parameterizing cut sets in a graphs by the number of their components, with Takehiro Ito, Daniël Paulusma, and Dimitrios M. Thilikos, ISAAC 2009, Honolulu, USA | doi | preprint | slides (by Daniël)
Reconfiguration of list edge-colorings in a graph, with Takehiro Ito and Erik Demaine, WADS 2009, Banff, Canada | doi | preprint | slides (by Takehiro)
Induced paths with parity restriction in claw-free graphs, with Pim van ‘t Hof and Daniël Paulusma, WG 2009, Montpellier, France | doi | preprint | slides (by Pim)
The plane-width of graphs, with Paul Medvedev and Martin Milanič, EuroComb 2009, Bordeaux, France | doi | preprint | slides
A note on k-colorability of P5-free graphs, with Chính Hoàng, Vadim Lozin, Joe Sawada, and Xiao Shu, MFCS 2008, Toruń, Poland | doi | preprint | slides
Journals
Beyond the Vizing’s bound for at most seven colors, with Łukasz Kowalik, SIAM Journal of Discrete Mathematics | preprint
Forbidding Kuratowski graphs as immersions, with Archontia C. Giannopoulou and Dimitrios M. Thilikos, Journal of Graph Theory | doi | preprint
Detecting fixed patterns in chordal graphs in polynomial time, with Rémy Belmonte, Petr Golovach, Pinar Heggernes, Pim van ‘t Hof, and Daniël Paulusma, Algorithmica, Volume 69(3) (2014), 501 - 521| doi | preprint
Lift contractions, with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos European Journal of Combinatorics (special issue for EuroComb 2011) Volume 35 (2014), 286 - 296 | doi | preprint
A note on contracting claw-free graphs, with Jiří Fiala and Daniël Paulusma, Discrete Mathematics and Theoretical Computer Science Volume 15 (2013), 223 - 232 | doi | preprint
Characterizing graphs of small carving-width, with Rémy Belmonte, Pim van ‘t Hof, and Daniël Paulusma and Dimitrios M. Thilikos, Discrete Applied Mathematics, Volume 161(13-14) (2013), 1888 - 1893 | doi | preprint
Increasing the minimum degree by contractions, with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos, Theoretical Computer Science, Volume 481 (2013), 74 – 84 | doi | preprint
Finding and listing induced paths and cycles, with Chính Hoàng, Joe Sawada, and R. Sritharan, Discrete Applied Mathematics, Volume 161(4-5) (2013), 633 - 641 | doi | preprint
Detecting induced star-like minors in polynomial time, with Jiří Fiala and Daniël Paulusma, Journal of Discrete Algorithms, Volume 17 (2012), 74 - 85 | doi | preprint
Reconfiguration of list edge-colorings in a graph, with Takehiro Ito and Erik Demaine, Discrete Applied Mathematics, Volume 160(15) (2012), 2199 - 2207 | doi |preprint
Complexity of independent set reconfigurability problems, with Paul Medvedev and Martin Milanič, Theoretical Computer Science, Volume 439 (2012), 9 - 15 | doi | preprint
Max-Cut and containment relations in graphs, Theoretical Computer Science, Volume 438 (2012), 89 - 95 | doi | preprint
On graph contractions and induced minors, with Pim van ‘t Hof, Daniël Paulusma, Stefan Szeider, and Dimitrios M. Thilikos, Discrete Applied Mathematics (special issue for GROW 2009) Volume 160(6) (2012), 799 – 809 | doi | preprint
Induced packing of odd cycles in a planar graph, with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos, Theoretical Computer Science 420 (2012), 28 - 35 | doi | preprint
Finding induced paths of given parity in claw-free graphs, with Pim van ‘t Hof and Daniël Paulusma, Algorithmica, Volume 62(1-2) (2012), 537 - 563| doi | preprint
The k-in-a-path problem for claw-free graphs, with Jiří Fiala, Bernard Lidický, and Daniël Paulusma, Algorithmica, Volume 62(1-2) (2012), 499 - 519 | doi | preprint
Containment relations in split graphs, with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos, Discrete Applied Mathematics, Volume 160(1-2) (2012), 155 - 163 | doi | preprint
Parameterizing cut sets in a graphs by the number of their components, with Takehiro Ito, Daniël Paulusma, and Dimitrios M. Thilikos, Theoretical Computer Science, Volume 412(45) (2011), 6340 - 6350 | doi | preprint
The plane-width of graphs, with Paul Medvedev and Martin Milanič, Journal of Graph Theory, Volume 68(3) (2011), 229 - 245 | doi | preprint
Shortest paths between shortest paths, with Paul Medvedev and Martin Milanič, Theoretical Computer Science, Volume 412(39) (2011), 5205 - 5210 | doi | preprint
On disconnected cuts and separators, with Takehiro Ito, Daniël Paulusma, and Dimitrios M. Thilikos, Discrete Applied Mathematics, Volume 159(13) (2011), 1345 - 1351 | doi | preprint
Contracting planar graphs to contractions of triangulations, with Daniël Paulusma and Dimitrios M. Thilikos, Journal of Discrete Algorithms, Volume 9(3) (2011), 299 - 306 | doi | preprint
The cops and robber game on graphs with forbidden (induced) subgraphs, with Gwenaël Joret and Dirk O. Theis, Contributions to Discrete Mathematics, Volume 5(2) (2010), 40 - 51 | doi (open access)
Deciding k-colorability of P5-free graphs in polynomial time, with Chính Hoàng, Vadim Lozin, Joe Sawada, and Xiao Shu, Algorithmica, Volume 57 (2010), 74 - 81 | doi | preprint
A note on the subgraphs of the (2x∞) grid, with Josep Diaz and Dimitrios M. Thilikos, Discrete Applied Mathematics, Volume 310 (2010), 531 - 536 | doi | preprint
Max-Cut and Max-Bisection are NP-hard on unit disk graphs, with Josep Diaz, Theoretical Computer Science, Volume 377 (2007), 271 - 276 | doi | preprint
Maximum k-regular induced subgraphs, with Domingos Cardoso and Vadim Lozin, Journal of Combinatorial Optimization, Volume 14 (2007), 455 - 463 | doi | preprint
Coloring edges and vertices of graphs without short or long cycles, with Vadim Lozin, Contributions to Discrete Mathematics, Volume 2 (2007), 61 - 66 | doi (open access)
An exact algorithm for Max-Cut in sparse graphs, with Federico Della Croce and Vangelis Paschos, Operations Research Letters, Volume 35 (2007), 403 - 408 | doi | preprint
Vertex 3-colorability of claw-free graphs, with Vadim Lozin, Algorithmic Operations Research, Volume 2 (2007), 15 - 21 | doi | preprint