Bonomo-Braberman, Flavia; Brettell, Nick; Munaro, Andrea; Paulusma, Daniël Solving problems on generalized convex graphs via mim-width. (English) Zbl 07783118 J. Comput. Syst. Sci. 140, Article ID 103493, 15 p. (2024). MSC: 68-XX PDFBibTeX XMLCite \textit{F. Bonomo-Braberman} et al., J. Comput. Syst. Sci. 140, Article ID 103493, 15 p. (2024; Zbl 07783118) Full Text: DOI
Bulteau, Laurent; Dabrowski, Konrad K.; Köhler, Noleen; Ordyniak, Sebastian; Paulusma, Daniël An algorithmic framework for locally constrained homomorphisms. (English) Zbl 07682405 Bekos, Michael A. (ed.) et al., Graph-theoretic concepts in computer science. 48th international workshop, WG 2022, Tübingen, Germany, June 22–24, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13453, 114-128 (2022). MSC: 68R10 PDFBibTeX XMLCite \textit{L. Bulteau} et al., Lect. Notes Comput. Sci. 13453, 114--128 (2022; Zbl 07682405) Full Text: DOI arXiv
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Ochem, Pascal; Paulusma, Daniël; Smith, Siani Acyclic, star, and injective colouring: bounding the diameter. (English) Zbl 1491.05074 Electron. J. Comb. 29, No. 2, Research Paper P2.43, 29 p. (2022). MSC: 05C15 05C78 05C85 05C12 05C45 PDFBibTeX XMLCite \textit{C. Brause} et al., Electron. J. Comb. 29, No. 2, Research Paper P2.43, 29 p. (2022; Zbl 1491.05074) Full Text: DOI
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration. (English) Zbl 1522.05362 J. Graph Theory 98, No. 1, 81-109 (2021). MSC: 05C70 05C62 PDFBibTeX XMLCite \textit{M. Bonamy} et al., J. Graph Theory 98, No. 1, 81--109 (2021; Zbl 1522.05362) Full Text: DOI arXiv OA License
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Paulusma, Daniël; Smith, Siani Acyclic, star, and injective colouring: bounding the diameter. (English) Zbl 07538588 Kowalik, Łukasz (ed.) et al., Graph-theoretic concepts in computer science. 47th international workshop, WG 2021, Warsaw, Poland, June 23–25, 2021. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12911, 336-348 (2021). MSC: 68R10 PDFBibTeX XMLCite \textit{C. Brause} et al., Lect. Notes Comput. Sci. 12911, 336--348 (2021; Zbl 07538588) Full Text: DOI arXiv
Bok, Jan; Jedličková, Nikola; Martin, Barnaby; Paulusma, Daniël; Smith, Siani Injective colouring for H-free graphs. (English) Zbl 07493522 Santhanam, Rahul (ed.) et al., Computer science – theory and applications. 16th international computer science symposium in Russia, CSR 2021, Sochi, Russia, June 28 – July 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12730, 18-30 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{J. Bok} et al., Lect. Notes Comput. Sci. 12730, 18--30 (2021; Zbl 07493522) Full Text: DOI
Bok, Jan; Jedličková, Nikola; Martin, Barnaby; Paulusma, Daniël; Smith, Siani Acyclic, star and injective colouring: a complexity picture for \(H\)-free graphs. (English) Zbl 07651161 Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 22, 22 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{J. Bok} et al., LIPIcs -- Leibniz Int. Proc. Inform. 173, Article 22, 22 p. (2020; Zbl 07651161) Full Text: DOI arXiv
Martin, Barnaby; Paulusma, Daniël; van Leeuwen, Erik Jan Disconnected cuts in claw-free graphs. (English) Zbl 1450.05073 J. Comput. Syst. Sci. 113, 60-75 (2020). MSC: 05C76 05C70 PDFBibTeX XMLCite \textit{B. Martin} et al., J. Comput. Syst. Sci. 113, 60--75 (2020; Zbl 1450.05073) Full Text: DOI Link
Gaspers, Serge; Huang, Shenwei; Paulusma, Daniël Colouring square-free graphs without long induced paths. (English) Zbl 1429.68081 J. Comput. Syst. Sci. 106, 60-79 (2019). MSC: 68Q25 05C15 68Q17 PDFBibTeX XMLCite \textit{S. Gaspers} et al., J. Comput. Syst. Sci. 106, 60--79 (2019; Zbl 1429.68081) Full Text: DOI arXiv Link
Paulusma, Daniël; Picouleau, Christophe; Ries, Bernard Critical vertices and edges in \(H\)-free graphs. (English) Zbl 1406.05037 Discrete Appl. Math. 257, 361-367 (2019). MSC: 05C15 PDFBibTeX XMLCite \textit{D. Paulusma} et al., Discrete Appl. Math. 257, 361--367 (2019; Zbl 1406.05037) Full Text: DOI arXiv
Martin, Barnaby; Paulusma, Daniël; van Leeuwen, Erik Jan Disconnected cuts in claw-free graphs. (English) Zbl 1524.05256 Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 61, 14 p. (2018). MSC: 05C76 05C40 05C70 68Q25 PDFBibTeX XMLCite \textit{B. Martin} et al., LIPIcs -- Leibniz Int. Proc. Inform. 112, Article 61, 14 p. (2018; Zbl 1524.05256) Full Text: DOI arXiv
Dabrowski, Konrad K.; Paulusma, Daniël On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs. (English) Zbl 1476.68200 Inf. Process. Lett. 134, 35-41 (2018). MSC: 68R10 05C15 05C85 68Q17 68Q25 PDFBibTeX XMLCite \textit{K. K. Dabrowski} and \textit{D. Paulusma}, Inf. Process. Lett. 134, 35--41 (2018; Zbl 1476.68200) Full Text: DOI arXiv
Chiarelli, Nina; Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity. (English) Zbl 1380.68219 Theor. Comput. Sci. 705, 75-83 (2018). MSC: 68Q25 05C85 68Q17 68R10 PDFBibTeX XMLCite \textit{N. Chiarelli} et al., Theor. Comput. Sci. 705, 75--83 (2018; Zbl 1380.68219) Full Text: DOI arXiv Link
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël Recognizing graphs close to bipartite graphs. (English) Zbl 1441.68167 Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 70, 14 p. (2017). MSC: 68R10 05C15 05C70 68Q17 68Q25 PDFBibTeX XMLCite \textit{M. Bonamy} et al., LIPIcs -- Leibniz Int. Proc. Inform. 83, Article 70, 14 p. (2017; Zbl 1441.68167) Full Text: DOI
Golovach, Petr A.; Johnson, Matthew; Martin, Barnaby; Paulusma, Daniël; Stewart, Anthony Surjective \(H\)-colouring: new hardness results. (English) Zbl 1489.68192 Kari, Jarkko (ed.) et al., Unveiling dynamics and complexity. 13th conference on computability in Europe, CiE 2017, Turku, Finland, June 12–16, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10307, 270-281 (2017). MSC: 68R10 05C15 05C60 68Q17 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Lect. Notes Comput. Sci. 10307, 270--281 (2017; Zbl 1489.68192) Full Text: DOI arXiv Link
Golovach, Petr A.; Johnson, Matthew; Paulusma, Daniël; Song, Jian A survey on the computational complexity of coloring graphs with forbidden subgraphs. (English) Zbl 1359.05039 J. Graph Theory 84, No. 4, 331-363 (2017). MSC: 05C15 05C60 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., J. Graph Theory 84, No. 4, 331--363 (2017; Zbl 1359.05039) Full Text: DOI arXiv Link
Paulusma, Daniël Open problems on graph coloring for special graph classes. (English) Zbl 1417.05077 Mayr, Ernst W. (ed.), Graph-theoretic concepts in computer science. 41st international workshop, WG 2015, Garching, Germany, June 17–19, 2015. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 9224, 16-30 (2016). MSC: 05C15 68Q17 PDFBibTeX XMLCite \textit{D. Paulusma}, Lect. Notes Comput. Sci. 9224, 16--30 (2016; Zbl 1417.05077) Full Text: DOI Link
Chaplick, Steven; Fiala, Jiří; van ’t Hof, Pim; Paulusma, Daniël; Tesař, Marek Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. (English) Zbl 1430.68122 Theor. Comput. Sci. 590, 86-95 (2015). MSC: 68Q25 05C60 68Q17 PDFBibTeX XMLCite \textit{S. Chaplick} et al., Theor. Comput. Sci. 590, 86--95 (2015; Zbl 1430.68122) Full Text: DOI arXiv
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan Induced disjoint paths in claw-free graphs. (English) Zbl 1311.05090 SIAM J. Discrete Math. 29, No. 1, 348-375 (2015). MSC: 05C38 05C85 68R10 68Q17 68Q25 68W40 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., SIAM J. Discrete Math. 29, No. 1, 348--375 (2015; Zbl 1311.05090) Full Text: DOI arXiv Link
Martin, Barnaby; Paulusma, Daniël The computational complexity of disconnected cut and \(2 K_2\)-partition. (English) Zbl 1307.05128 J. Comb. Theory, Ser. B 111, 17-37 (2015). MSC: 05C40 05C60 05C70 68Q17 PDFBibTeX XMLCite \textit{B. Martin} and \textit{D. Paulusma}, J. Comb. Theory, Ser. B 111, 17--37 (2015; Zbl 1307.05128) Full Text: DOI
Johnson, Matthew; Patel, Viresh; Paulusma, Daniël; Trunck, Théophile Obtaining online ecological colourings by generalizing first-fit. (English) Zbl 1380.68454 Theory Comput. Syst. 54, No. 2, 244-260 (2014). MSC: 68W27 05C15 05C85 PDFBibTeX XMLCite \textit{M. Johnson} et al., Theory Comput. Syst. 54, No. 2, 244--260 (2014; Zbl 1380.68454) Full Text: DOI Link
Chalopin, Jérémie; Paulusma, Daniël Packing bipartite graphs with covers of complete bipartite graphs. (English) Zbl 1285.05146 Discrete Appl. Math. 168, 40-50 (2014). MSC: 05C70 05C60 PDFBibTeX XMLCite \textit{J. Chalopin} and \textit{D. Paulusma}, Discrete Appl. Math. 168, 40--50 (2014; Zbl 1285.05146) Full Text: DOI
Golovach, Petr A.; Paulusma, Daniël; Song, Jian Coloring graphs without short cycles and long induced paths. (English) Zbl 1284.05098 Discrete Appl. Math. 167, 107-120 (2014). MSC: 05C15 05C38 05C60 68Q17 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Discrete Appl. Math. 167, 107--120 (2014; Zbl 1284.05098) Full Text: DOI
Golovach, Petr A.; Lidický, Bernard; Martin, Barnaby; Paulusma, Daniël Finding vertex-surjective graph homomorphisms. (English) Zbl 1253.68149 Acta Inf. 49, No. 6, 381-394 (2012). MSC: 68Q17 05C60 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Acta Inf. 49, No. 6, 381--394 (2012; Zbl 1253.68149) Full Text: DOI Link
Golovach, Petr A.; Paulusma, Daniël; Song, Jian Computing vertex-surjective homomorphisms to partially reflexive trees. (English) Zbl 1251.05031 Theor. Comput. Sci. 457, 86-100 (2012). MSC: 05C05 05C60 68Q17 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Theor. Comput. Sci. 457, 86--100 (2012; Zbl 1251.05031) Full Text: DOI
Heggernes, Pinar; Van ’t Hof, Pim; Paulusma, Daniël Computing role assignments of proper interval graphs in polynomial time. (English) Zbl 1247.05240 J. Discrete Algorithms 14, 173-188 (2012). MSC: 05C85 68W40 PDFBibTeX XMLCite \textit{P. Heggernes} et al., J. Discrete Algorithms 14, 173--188 (2012; Zbl 1247.05240) Full Text: DOI
Fiala, Jiří; Kamiński, Marcin; Lidický, Bernard; Paulusma, Daniël The \(k\)-in-a-path problem for claw-free graphs. (English) Zbl 1236.68088 Algorithmica 62, No. 1-2, 499-519 (2012). MSC: 68Q17 05C85 PDFBibTeX XMLCite \textit{J. Fiala} et al., Algorithmica 62, No. 1--2, 499--519 (2012; Zbl 1236.68088) Full Text: DOI
Golovach, Petr A.; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M. Induced packing of odd cycles in planar graphs. (English) Zbl 1232.68064 Theor. Comput. Sci. 420, 28-35 (2012). MSC: 68Q17 05C70 05C85 68R10 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Theor. Comput. Sci. 420, 28--35 (2012; Zbl 1232.68064) Full Text: DOI
Ito, Takehiro; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M. Parameterizing cut sets in a graph by the number of their components. (English) Zbl 1232.05115 Theor. Comput. Sci. 412, No. 45, 6340-6350 (2011). MSC: 05C40 68Q17 PDFBibTeX XMLCite \textit{T. Ito} et al., Theor. Comput. Sci. 412, No. 45, 6340--6350 (2011; Zbl 1232.05115) Full Text: DOI
Ito, Takehiro; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M. On disconnected cuts and separators. (English) Zbl 1223.05155 Discrete Appl. Math. 159, No. 13, 1345-1351 (2011). MSC: 05C40 PDFBibTeX XMLCite \textit{T. Ito} et al., Discrete Appl. Math. 159, No. 13, 1345--1351 (2011; Zbl 1223.05155) Full Text: DOI
Golovach, Petr A.; Paulusma, Daniël; Song, Jian Computing vertex-surjective homomorphisms to partially reflexive trees. (English) Zbl 1332.68073 Kulikov, Alexander (ed.) et al., Computer science – theory and applications. 6th international computer science symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20711-2/pbk). Lecture Notes in Computer Science 6651, 261-274 (2011). MSC: 68Q25 05C05 05C60 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Lect. Notes Comput. Sci. 6651, 261--274 (2011; Zbl 1332.68073) Full Text: DOI Link
Johnson, Matthew; Paulusma, Daniël; Wood, Chantal Path factors and parallel knock-out schemes of almost claw-free graphs. (English) Zbl 1219.05140 Discrete Math. 310, No. 9, 1413-1423 (2010). MSC: 05C70 05C38 05C35 PDFBibTeX XMLCite \textit{M. Johnson} et al., Discrete Math. 310, No. 9, 1413--1423 (2010; Zbl 1219.05140) Full Text: DOI Link
Fiala, Jiří; Paulusma, Daniël Comparing universal covers in polynomial time. (English) Zbl 1142.68456 Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 158-167 (2008). MSC: 68R10 05C70 05C85 90C59 PDFBibTeX XMLCite \textit{J. Fiala} and \textit{D. Paulusma}, Lect. Notes Comput. Sci. 5010, 158--167 (2008; Zbl 1142.68456) Full Text: DOI Link
Fiala, Jiří; Paulusma, Daniël; Telle, Jan Arne Locally constrained graph homomorphisms and equitable partitions. (English) Zbl 1205.05141 Eur. J. Comb. 29, No. 4, 850-880 (2008). MSC: 05C50 05C07 05C60 05C70 05C85 68Q25 PDFBibTeX XMLCite \textit{J. Fiala} et al., Eur. J. Comb. 29, No. 4, 850--880 (2008; Zbl 1205.05141) Full Text: DOI Link