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
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
Bodirsky, Manuel; Martin, Barnaby; Pinsker, Michael; Pongrácz, András Constraint satisfaction problems for reducts of homogeneous graphs. (English) Zbl 1430.68121 SIAM J. Comput. 48, No. 4, 1224-1264 (2019). MSC: 68Q25 03C15 05C55 05C75 08A70 PDFBibTeX XMLCite \textit{M. Bodirsky} et al., SIAM J. Comput. 48, No. 4, 1224--1264 (2019; Zbl 1430.68121) Full Text: DOI
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
Madelaine, Florent R.; Martin, Barnaby Consistency for counting quantifiers. (English) Zbl 1510.68031 Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 11, 13 p. (2018). MSC: 68Q25 03B70 08A70 PDFBibTeX XMLCite \textit{F. R. Madelaine} and \textit{B. Martin}, LIPIcs -- Leibniz Int. Proc. Inform. 117, Article 11, 13 p. (2018; Zbl 1510.68031) Full Text: DOI
Martin, Barnaby Quantified constraints in twenty seventeen. (English) Zbl 1482.68168 Krokhin, Andrei (ed.) et al., The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. Dagstuhl Follow-Ups 7, 327-346 (2017). MSC: 68R07 08A70 68Q25 68Q27 PDFBibTeX XMLCite \textit{B. Martin}, Dagstuhl Follow-Ups 7, 327--346 (2017; Zbl 1482.68168) Full Text: DOI
Glaßer, Christian; Jonsson, Peter; Martin, Barnaby Circuit satisfiability and constraint satisfaction around Skolem arithmetic. (English) Zbl 1380.68221 Theor. Comput. Sci. 703, 18-36 (2017). MSC: 68Q25 03F30 PDFBibTeX XMLCite \textit{C. Glaßer} et al., Theor. Comput. Sci. 703, 18--36 (2017; Zbl 1380.68221) Full Text: DOI Link
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
Đapić, Petar; Marković, Petar; Martin, Barnaby Quantified constraint satisfaction problem on semicomplete digraphs. (English) Zbl 1367.68115 ACM Trans. Comput. Log. 18, No. 1, Article No. 2, 47 p. (2017). MSC: 68Q25 05C20 05C85 68Q17 PDFBibTeX XMLCite \textit{P. Đapić} et al., ACM Trans. Comput. Log. 18, No. 1, Article No. 2, 47 p. (2017; Zbl 1367.68115) Full Text: DOI Link
Martin, Barnaby; Pongrácz, András; Wrona, Michał The complexity of counting quantifiers on equality languages. (English) Zbl 1359.68138 Theor. Comput. Sci. 670, 56-67 (2017). MSC: 68Q25 03B70 PDFBibTeX XMLCite \textit{B. Martin} et al., Theor. Comput. Sci. 670, 56--67 (2017; Zbl 1359.68138) Full Text: DOI Link
Martin, Barnaby; Pongrácz, András; Wrona, Michał The complexity of counting quantifiers on equality languages. (English) Zbl 1476.68113 Beckmann, Arnold (ed.) et al., Pursuit of the universal. 12th conference on computability in Europe, CiE 2016, Paris, France, June 27 – July 1, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9709, 333-342 (2016). MSC: 68Q25 03B70 PDFBibTeX XMLCite \textit{B. Martin} et al., Lect. Notes Comput. Sci. 9709, 333--342 (2016; Zbl 1476.68113) Full Text: DOI Link
Glaßer, Christian; Jonsson, Peter; Martin, Barnaby Circuit satisfiability and constraint satisfaction around Skolem arithmetic. (English) Zbl 1475.68123 Beckmann, Arnold (ed.) et al., Pursuit of the universal. 12th conference on computability in Europe, CiE 2016, Paris, France, June 27 – July 1, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9709, 323-332 (2016). MSC: 68Q06 03B25 03F30 68Q25 PDFBibTeX XMLCite \textit{C. Glaßer} et al., Lect. Notes Comput. Sci. 9709, 323--332 (2016; Zbl 1475.68123) Full Text: DOI Link
Bodirsky, Manuel; Dalmau, Victor; Martin, Barnaby; Mottet, Antoine; Pinsker, Michael Distance constraint satisfaction problems. (English) Zbl 1336.68116 Inf. Comput. 247, 87-105 (2016). MSC: 68Q25 03B70 68Q17 PDFBibTeX XMLCite \textit{M. Bodirsky} et al., Inf. Comput. 247, 87--105 (2016; Zbl 1336.68116) Full Text: DOI arXiv
Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine Constraint satisfaction problems over the integers with successor. (English) Zbl 1440.68111 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 256-267 (2015). MSC: 68Q25 03B70 PDFBibTeX XMLCite \textit{M. Bodirsky} et al., Lect. Notes Comput. Sci. 9134, 256--267 (2015; Zbl 1440.68111) Full Text: DOI arXiv Link
Martin, Barnaby; Madelaine, Florent; Stacho, Juraj Constraint satisfaction with counting quantifiers. (English) Zbl 1392.68206 SIAM J. Discrete Math. 29, No. 2, 1065-1113 (2015). MSC: 68Q25 68Q17 68R10 PDFBibTeX XMLCite \textit{B. Martin} et al., SIAM J. Discrete Math. 29, No. 2, 1065--1113 (2015; Zbl 1392.68206) Full Text: DOI 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
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
Bodirsky, Manuel; Kára, Jan; Martin, Barnaby The complexity of surjective homomorphism problems-a survey. (English) Zbl 1246.05104 Discrete Appl. Math. 160, No. 12, 1680-1690 (2012). MSC: 05C60 68Q17 PDFBibTeX XMLCite \textit{M. Bodirsky} et al., Discrete Appl. Math. 160, No. 12, 1680--1690 (2012; Zbl 1246.05104) Full Text: DOI
Martin, Barnaby Low-level dichotomy for quantified constraint satisfaction problems. (English) Zbl 1260.68159 Inf. Process. Lett. 111, No. 20, 999-1003 (2011). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{B. Martin}, Inf. Process. Lett. 111, No. 20, 999--1003 (2011; Zbl 1260.68159) Full Text: DOI arXiv
Martin, Barnaby First-order model checking problems parameterized by the model. (English) Zbl 1142.68439 Beckmann, Arnold (ed.) et al., Logic and theory of algorithms. 4th conference on computability in Europe, CiE 2008, Athens, Greece, June 15–20, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69405-2/pbk). Lecture Notes in Computer Science 5028, 417-427 (2008). MSC: 68Q60 03B70 PDFBibTeX XMLCite \textit{B. Martin}, Lect. Notes Comput. Sci. 5028, 417--427 (2008; Zbl 1142.68439) Full Text: DOI