Kim, Hyobeen; Siggers, Mark Towards a dichotomy for the list switch homomorphism problem for signed graphs. (English) Zbl 07796796 Kyungpook Math. J. 63, No. 3, 355-372 (2023). MSC: 05C15 05C85 PDFBibTeX XMLCite \textit{H. Kim} and \textit{M. Siggers}, Kyungpook Math. J. 63, No. 3, 355--372 (2023; Zbl 07796796) Full Text: DOI
Heo, Cheolwon; Kim, Hyobin; Mark, Siggers The complexity of the matroid homomorphism problem. (English) Zbl 1516.05021 Electron. J. Comb. 30, No. 2, Research Paper P2.28, 17 p. (2023). MSC: 05B35 52B40 68Q25 PDFBibTeX XMLCite \textit{C. Heo} et al., Electron. J. Comb. 30, No. 2, Research Paper P2.28, 17 p. (2023; Zbl 1516.05021) Full Text: DOI
Chudnovsky, Maria; Huang, Shenwei; Rzążewski, Paweł; Spirkl, Sophie; Zhong, Mingxian Complexity of \(C_k\)-coloring in hereditary classes of graphs. (English) Zbl 07687210 Inf. Comput. 292, Article ID 105015, 19 p. (2023). MSC: 68Qxx PDFBibTeX XMLCite \textit{M. Chudnovsky} et al., Inf. Comput. 292, Article ID 105015, 19 p. (2023; Zbl 07687210) Full Text: DOI
Bok, Jan; Brewster, Richard; Feder, Tomás; Hell, Pavol; Jedličková, Nikola List homomorphism problems for signed trees. (English) Zbl 1506.05082 Discrete Math. 346, No. 3, Article ID 113257, 24 p. (2023). MSC: 05C22 05C05 68Q15 05C60 PDFBibTeX XMLCite \textit{J. Bok} et al., Discrete Math. 346, No. 3, Article ID 113257, 24 p. (2023; Zbl 1506.05082) Full Text: DOI
Bhyravarapu, Sriram; Jana, Satyabrata; Panolan, Fahad; Saurabh, Saket; Verma, Shaily List homomorphism: beyond the known boundaries. (English) Zbl 07719369 Castañeda, Armando (ed.) et al., Latin 2022: theoretical informatics. 15th Latin American symposium, Guanajuato, Mexico, November 7–11, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13568, 593-609 (2022). MSC: 68Qxx 68Rxx 68Wxx PDFBibTeX XMLCite \textit{S. Bhyravarapu} et al., Lect. Notes Comput. Sci. 13568, 593--609 (2022; Zbl 07719369) Full Text: DOI
Bok, Jan; Brewster, Richard; Feder, Tomás; Hell, Pavol; Jedličková, Nikola List homomorphisms to separable signed graphs. (English) Zbl 07683160 Balachandran, Niranjan (ed.) et al., Algorithms and discrete applied mathematics. 8th international conference, CALDAM 2022, Puducherry, India, February 10–12, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13179, 22-35 (2022). MSC: 68Wxx PDFBibTeX XMLCite \textit{J. Bok} et al., Lect. Notes Comput. Sci. 13179, 22--35 (2022; Zbl 07683160) Full Text: DOI
Bokal, Drago; Jerebic, Janja Guarding a subgraph as a tool in pursuit-evasion games. (English) Zbl 1483.05101 Discuss. Math., Graph Theory 42, No. 1, 123-138 (2022). Reviewer: Solden Stoll (Seattle) MSC: 05C57 05C60 91A43 94A24 PDFBibTeX XMLCite \textit{D. Bokal} and \textit{J. Jerebic}, Discuss. Math., Graph Theory 42, No. 1, 123--138 (2022; Zbl 1483.05101) Full Text: DOI
Focke, Jacob; Goldberg, Leslie Ann; Roth, Marc; Živný, Stanislav Counting homomorphisms to \(K_4\)-minor-free graphs, modulo 2. (English) Zbl 07436465 SIAM J. Discrete Math. 35, No. 4, 2749-2814 (2021). MSC: 68R10 05C60 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Focke} et al., SIAM J. Discrete Math. 35, No. 4, 2749--2814 (2021; Zbl 07436465) Full Text: DOI arXiv
Campos, Victor A.; Gomes, Guilherme C. M.; Ibiapina, Allen; Lopes, Raul; Sau, Ignasi; Silva, Ana Coloring problems on bipartite graphs of small diameter. (English) Zbl 1464.05143 Electron. J. Comb. 28, No. 2, Research Paper P2.14, 26 p. (2021). MSC: 05C15 05C12 68Q17 PDFBibTeX XMLCite \textit{V. A. Campos} et al., Electron. J. Comb. 28, No. 2, Research Paper P2.14, 26 p. (2021; Zbl 1464.05143) Full Text: DOI arXiv
Okrasa, Karolina; Rzążewski, Paweł Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs. (English) Zbl 1511.68126 SIAM J. Comput. 50, No. 2, 487-508 (2021). MSC: 68Q25 05C60 05C85 68Q27 68R10 PDFBibTeX XMLCite \textit{K. Okrasa} and \textit{P. Rzążewski}, SIAM J. Comput. 50, No. 2, 487--508 (2021; Zbl 1511.68126) Full Text: DOI arXiv
Briceño, Raimundo; Bulatov, Andrei; Dalmau, Víctor; Larose, Benoît Dismantlability, connectedness, and mixing in relational structures. (English) Zbl 1503.08002 J. Comb. Theory, Ser. B 147, 37-70 (2021). MSC: 08A70 05C90 60C05 68Q87 82B20 PDFBibTeX XMLCite \textit{R. Briceño} et al., J. Comb. Theory, Ser. B 147, 37--70 (2021; Zbl 1503.08002) Full Text: DOI arXiv Link
Chen, Hubie; Jansen, Bart M. P.; Okrasa, Karolina; Pieterse, Astrid; Rzążewski, Paweł Sparsification lower bounds for list \(H\)-coloring. (English) Zbl 07765416 Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 58, 17 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{H. Chen} et al., LIPIcs -- Leibniz Int. Proc. Inform. 181, Article 58, 17 p. (2020; Zbl 07765416) Full Text: DOI arXiv
Okrasa, Karolina; Piecyk, Marta; Rzążewski, Paweł Full complexity classification of the list homomorphism problem for bounded-treewidth graphs. (English) Zbl 07651213 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 74, 24 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{K. Okrasa} et al., LIPIcs -- Leibniz Int. Proc. Inform. 173, Article 74, 24 p. (2020; Zbl 07651213) Full Text: DOI arXiv
Bok, Jan; Brewster, Richard; Feder, Tomás; Hell, Pavol; Jedličková, Nikola List homomorphism problems for signed graphs. (English) Zbl 07559391 Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 20, 14 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{J. Bok} et al., LIPIcs -- Leibniz Int. Proc. Inform. 170, Article 20, 14 p. (2020; Zbl 07559391) Full Text: DOI arXiv
Hell, Pavol; Huang, Jing; McConnell, Ross M.; Rafiey, Arash Min-orderable digraphs. (English) Zbl 1450.05036 SIAM J. Discrete Math. 34, No. 3, 1710-1724 (2020). MSC: 05C20 05C75 05C62 05C17 PDFBibTeX XMLCite \textit{P. Hell} et al., SIAM J. Discrete Math. 34, No. 3, 1710--1724 (2020; Zbl 1450.05036) Full Text: DOI
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
Feder, Tomás; Hell, Pavol Complexity of correspondence \(H\)-colourings. (English) Zbl 1440.05150 Discrete Appl. Math. 281, 235-245 (2020). MSC: 05C60 05C15 68Q17 PDFBibTeX XMLCite \textit{T. Feder} and \textit{P. Hell}, Discrete Appl. Math. 281, 235--245 (2020; Zbl 1440.05150) Full Text: DOI arXiv
Haney, Samuel; Liaee, Mehraneh; Maggs, Bruce M.; Panigrahi, Debmalya; Rajaraman, Rajmohan; Sundaram, Ravi Retracting graphs to cycles. (English) Zbl 07561563 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 70, 15 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{S. Haney} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 70, 15 p. (2019; Zbl 07561563) Full Text: DOI arXiv
Chudnovsky, Maria; Huang, Shenwei; Rzążewski, Paweł; Spirkl, Sophie; Zhong, Mingxian Complexity of \(C_K\)-coloring in hereditary classes of graphs. (English) Zbl 07525468 Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 31, 15 p. (2019). MSC: 68Wxx PDFBibTeX XMLCite \textit{M. Chudnovsky} et al., LIPIcs -- Leibniz Int. Proc. Inform. 144, Article 31, 15 p. (2019; Zbl 07525468) Full Text: DOI arXiv
Focke, Jacob; Goldberg, Leslie Ann; Živný, Stanislav The complexity of counting surjective homomorphisms and compactions. (English) Zbl 1429.05143 SIAM J. Discrete Math. 33, No. 2, 1006-1043 (2019). MSC: 05C60 05C30 PDFBibTeX XMLCite \textit{J. Focke} et al., SIAM J. Discrete Math. 33, No. 2, 1006--1043 (2019; Zbl 1429.05143) 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
Hell, Pavol; Huang, Jing; McConnell, Ross M.; Rafiey, Arash Interval-like graphs and digraphs. (English) Zbl 1494.68195 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 68, 13 p. (2018). MSC: 68R10 05C85 PDFBibTeX XMLCite \textit{P. Hell} et al., LIPIcs -- Leibniz Int. Proc. Inform. 117, Article 68, 13 p. (2018; Zbl 1494.68195) Full Text: DOI arXiv
Vikas, Narayan Computational complexity relationship between compaction, vertex-compaction, and retraction. (English) Zbl 1410.68181 J. Discrete Algorithms 52-53, 168-181 (2018). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{N. Vikas}, J. Discrete Algorithms 52--53, 168--181 (2018; Zbl 1410.68181) Full Text: DOI
Valadkhan, Payam; Davari, Mohammad-Javad The monotonicity property of \(M\)-partition problems. (English) Zbl 1384.05134 Eur. J. Comb. 70, 178-189 (2018). MSC: 05C70 68Q25 PDFBibTeX XMLCite \textit{P. Valadkhan} and \textit{M.-J. Davari}, Eur. J. Comb. 70, 178--189 (2018; Zbl 1384.05134) Full Text: DOI
Larose, Benoit; Siggers, Mark NU polymorphisms on reflexive digraphs. (English) Zbl 1383.05134 SIAM J. Discrete Math. 32, No. 1, 728-749 (2018). MSC: 05C20 05C75 08B05 06A07 PDFBibTeX XMLCite \textit{B. Larose} and \textit{M. Siggers}, SIAM J. Discrete Math. 32, No. 1, 728--749 (2018; Zbl 1383.05134) Full Text: DOI
Larose, Benoit Algebra and the complexity of digraph CSPs: a survey. (English) Zbl 1482.68166 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, 267-285 (2017). MSC: 68R07 05C20 08A70 68Q25 68R10 PDFBibTeX XMLCite \textit{B. Larose}, Dagstuhl Follow-Ups 7, 267--285 (2017; Zbl 1482.68166) Full Text: DOI
Barto, Libor; Krokhin, Andrei; Willard, Ross Polymorphisms, and how to use them. (English) Zbl 1482.68161 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, 1-44 (2017). MSC: 68R07 08A70 68Q25 PDFBibTeX XMLCite \textit{L. Barto} et al., Dagstuhl Follow-Ups 7, 1--44 (2017; Zbl 1482.68161) Full Text: DOI
Vikas, Narayan Computational complexity of graph partition under vertex-compaction to an irreflexive hexagon. (English) Zbl 1441.68197 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 69, 14 p. (2017). MSC: 68R10 05C70 05C85 68Q17 68Q25 PDFBibTeX XMLCite \textit{N. Vikas}, LIPIcs -- Leibniz Int. Proc. Inform. 83, Article 69, 14 p. (2017; Zbl 1441.68197) Full Text: DOI
Feder, Tomás; Hell, Pavol Correspondence homomorphisms to reflexive graphs. (English) Zbl 1383.05212 Bassino, Frédérique (ed.) et al., LAGOS 2017. Selected papers of the 9th Latin-American algorithms, graphs, and optimization symposium, Marseille, France, September 11–15, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 62, 9-14 (2017). MSC: 05C60 05C15 68Q25 PDFBibTeX XMLCite \textit{T. Feder} and \textit{P. Hell}, Electron. Notes Discrete Math. 62, 9--14 (2017; Zbl 1383.05212) Full Text: DOI
Foucaud, Florent; Harutyunyan, Ararat; Hell, Pavol; Legay, Sylvain; Manoussakis, Yannis; Naserasr, Reza The complexity of tropical graph homomorphisms. (English) Zbl 1367.05141 Discrete Appl. Math. 229, 64-81 (2017). MSC: 05C60 05C15 PDFBibTeX XMLCite \textit{F. Foucaud} et al., Discrete Appl. Math. 229, 64--81 (2017; Zbl 1367.05141) Full Text: DOI arXiv
Chitnis, Rajesh; Egri, László; Marx, Dániel List H-coloring a graph by removing few vertices. (English) Zbl 1361.05085 Algorithmica 78, No. 1, 110-146 (2017). MSC: 05C60 05C15 05D15 68Q25 PDFBibTeX XMLCite \textit{R. Chitnis} et al., Algorithmica 78, No. 1, 110--146 (2017; Zbl 1361.05085) Full Text: DOI arXiv
Valadkhan, Payam The complexity of list edge-partitions for simple graphs. (English) Zbl 1352.05154 Eur. J. Comb. 61, 219-234 (2017). MSC: 05C70 PDFBibTeX XMLCite \textit{P. Valadkhan}, Eur. J. Comb. 61, 219--234 (2017; Zbl 1352.05154) Full Text: DOI
Yoshida, Yuichi Testing list \(H\)-homomorphisms. (English) Zbl 1353.68139 Comput. Complexity 25, No. 4, 737-773 (2016). MSC: 68Q25 05C60 08A70 68W20 PDFBibTeX XMLCite \textit{Y. Yoshida}, Comput. Complexity 25, No. 4, 737--773 (2016; Zbl 1353.68139) Full Text: DOI
Hell, Pavol; Nevisi, Mayssam Mohammadi Minimum cost homomorphisms with constrained costs. (English) Zbl 1476.68110 Dinh, Thang N. (ed.) et al., Computing and combinatorics. 22nd international conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2–4, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9797, 194-206 (2016). MSC: 68Q25 05C60 68Q17 68R10 PDFBibTeX XMLCite \textit{P. Hell} and \textit{M. M. Nevisi}, Lect. Notes Comput. Sci. 9797, 194--206 (2016; Zbl 1476.68110) Full Text: DOI arXiv
Bulatov, Andrei A. Conservative constraint satisfaction re-revisited. (English) Zbl 1346.68108 J. Comput. Syst. Sci. 82, No. 2, 347-356 (2016). MSC: 68Q25 PDFBibTeX XMLCite \textit{A. A. Bulatov}, J. Comput. Syst. Sci. 82, No. 2, 347--356 (2016; Zbl 1346.68108) Full Text: DOI arXiv
Kolman, Petr; Koutecký, Martin Extended formulation for CSP that is compact for instances of bounded treewidth. (English) Zbl 1393.68073 Electron. J. Comb. 22, No. 4, Research Paper P4.30, 14 p. (2015). MSC: 68Q25 68Q17 68R10 90C05 PDFBibTeX XMLCite \textit{P. Kolman} and \textit{M. Koutecký}, Electron. J. Comb. 22, No. 4, Research Paper P4.30, 14 p. (2015; Zbl 1393.68073) Full Text: arXiv Link
Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting list matrix partitions of graphs. (English) Zbl 1329.68139 SIAM J. Comput. 44, No. 4, 1089-1118 (2015). MSC: 68Q25 05C30 05C50 68Q17 PDFBibTeX XMLCite \textit{A. Göbel} et al., SIAM J. Comput. 44, No. 4, 1089--1118 (2015; Zbl 1329.68139) Full Text: DOI arXiv
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
Hell, Pavol Graph partitions with prescribed patterns. (English) Zbl 1292.05214 Eur. J. Comb. 35, 335-353 (2014). MSC: 05C70 05C69 05C15 05C50 PDFBibTeX XMLCite \textit{P. Hell}, Eur. J. Comb. 35, 335--353 (2014; Zbl 1292.05214) Full Text: DOI
Hell, Pavol; Siggers, Mark Semilattice polymorphisms and chordal graphs. (English) Zbl 1284.05125 Eur. J. Comb. 36, 694-706 (2014). MSC: 05C25 PDFBibTeX XMLCite \textit{P. Hell} and \textit{M. Siggers}, Eur. J. Comb. 36, 694--706 (2014; Zbl 1284.05125) Full Text: DOI
Vikas, Narayan Algorithms for partition of some class of graphs under compaction and vertex-compaction. (English) Zbl 1275.05057 Algorithmica 67, No. 2, 180-206 (2013). MSC: 05C85 05C70 68Q17 PDFBibTeX XMLCite \textit{N. Vikas}, Algorithmica 67, No. 2, 180--206 (2013; Zbl 1275.05057) Full Text: DOI
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
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
Feder, Tomás; Hell, Pavol; Huang, Jing; Rafiey, Arash Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. (English) Zbl 1236.05092 Discrete Appl. Math. 160, No. 6, 697-707 (2012). MSC: 05C20 05C85 PDFBibTeX XMLCite \textit{T. Feder} et al., Discrete Appl. Math. 160, No. 6, 697--707 (2012; Zbl 1236.05092) 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
Gutin, Gregory; Kim, Eun Jung The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops. (English) Zbl 1225.05113 Discrete Appl. Math. 158, No. 4, 319-330 (2010). MSC: 05C20 05C60 05C85 PDFBibTeX XMLCite \textit{G. Gutin} and \textit{E. J. Kim}, Discrete Appl. Math. 158, No. 4, 319--330 (2010; Zbl 1225.05113) Full Text: DOI
Cook, Kathryn; Dantas, Simone; Eschen, Elaine M.; Faria, Luerbio; de Figueiredo, Celina M. H.; Klein, Sulamita \(2K_{2}\) vertex-set partition into nonempty parts. (English) Zbl 1230.05233 Discrete Math. 310, No. 6-7, 1259-1264 (2010). MSC: 05C70 05A18 05C85 68Q17 PDFBibTeX XMLCite \textit{K. Cook} et al., Discrete Math. 310, No. 6--7, 1259--1264 (2010; Zbl 1230.05233) Full Text: DOI
Feder, Tomás; Hell, Pavol; Huang, Jing; Rafiey, Arash Adjusted interval digraphs. (English) Zbl 1267.05257 Koster, Arie (ed.) et al., DIMAP workshop on algorithmic graph theory. Extended abstracts from the workshop held at the University of Warwick, Coventry, UK, March 23–25, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 32, 83-91 (2009). MSC: 05C85 05C20 PDFBibTeX XMLCite \textit{T. Feder} et al., Electron. Notes Discrete Math. 32, 83--91 (2009; Zbl 1267.05257) Full Text: DOI
Feder, Tomas; Hell, Pavol; Huang, Jing Extension problems with degree bounds. (English) Zbl 1177.05037 Discrete Appl. Math. 157, No. 7, 1592-1599 (2009). MSC: 05C15 05C85 68Q25 PDFBibTeX XMLCite \textit{T. Feder} et al., Discrete Appl. Math. 157, No. 7, 1592--1599 (2009; Zbl 1177.05037) Full Text: DOI
Hell, Pavol; Nešetřil, Jaroslav Colouring, constraint satisfaction, and complexity. (English) Zbl 1302.68251 Comput. Sci. Rev. 2, No. 3, 143-163 (2008). MSC: 68T20 05C15 68Q25 68-02 PDFBibTeX XMLCite \textit{P. Hell} and \textit{J. Nešetřil}, Comput. Sci. Rev. 2, No. 3, 143--163 (2008; Zbl 1302.68251) Full Text: DOI
Díaz, Josep; Serna, Maria; Thilikos, Dimitrios M. Efficient algorithms for counting parameterized list \(H\)-colorings. (English) Zbl 1160.68024 J. Comput. Syst. Sci. 74, No. 5, 919-937 (2008). MSC: 68R10 05C15 05C85 68Q25 PDFBibTeX XMLCite \textit{J. Díaz} et al., J. Comput. Syst. Sci. 74, No. 5, 919--937 (2008; Zbl 1160.68024) Full Text: DOI
Dantas, Simone; Eschen, Elaine M.; Faria, Luerbio; De Figueiredo, Celina M. H.; Klein, Sulamita \(2K_2\) vertex-set partition into nonempty parts. (English) Zbl 1341.05205 Liebling, Th. (ed.) et al., The IV Latin-American algorithms, graphs, and optimization symposium, Puerto Varas, Chile, November 25–29, 2007. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 30, 291-296 (2008). MSC: 05C70 05A18 05C10 68W40 68Q17 PDFBibTeX XMLCite \textit{S. Dantas} et al., Electron. Notes Discrete Math. 30, 291--296 (2008; Zbl 1341.05205) Full Text: DOI
Färnqvist, Tommy; Jonsson, Peter Bounded tree-width and CSP-related problems. (English) Zbl 1193.68130 Tokuyama, Takeshi (ed.), Algorithms and computation. 18th international symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-77118-0/pbk). Lecture Notes in Computer Science 4835, 632-643 (2007). MSC: 68Q25 05C05 05C85 68Q17 68R10 68W25 PDFBibTeX XMLCite \textit{T. Färnqvist} and \textit{P. Jonsson}, Lect. Notes Comput. Sci. 4835, 632--643 (2007; Zbl 1193.68130) Full Text: DOI
Díaz, Josep; Serna, Maria; Thilikos, Dimitrios M. Complexity issues on bounded restrictive \(H\)-coloring. (English) Zbl 1119.05042 Discrete Math. 307, No. 16, 2082-2093 (2007). MSC: 05C15 68Q25 68R10 PDFBibTeX XMLCite \textit{J. Díaz} et al., Discrete Math. 307, No. 16, 2082--2093 (2007; Zbl 1119.05042) Full Text: DOI
Feder, Tomás; Hell, Pavol; Huang, Jing The structure of bi-arc trees. (English) Zbl 1110.05093 Discrete Math. 307, No. 3-5, 393-401 (2007). MSC: 05C85 05C75 05C05 68R10 PDFBibTeX XMLCite \textit{T. Feder} et al., Discrete Math. 307, No. 3--5, 393--401 (2007; Zbl 1110.05093) Full Text: DOI
Feder, Tomás; Hell, Pavol; Huang, Jing List homomorphisms of graphs with bounded degrees. (English) Zbl 1111.05035 Discrete Math. 307, No. 3-5, 386-392 (2007). MSC: 05C15 05C85 68R10 PDFBibTeX XMLCite \textit{T. Feder} et al., Discrete Math. 307, No. 3--5, 386--392 (2007; Zbl 1111.05035) Full Text: DOI
Dantas, Simone; De Figueiredo, Celina M. H.; Gravier, Sylvain; Klein, Sulamita Extended skew partition problem. (English) Zbl 1178.68640 Discrete Math. 306, No. 19-20, 2438-2449 (2006). MSC: 68W05 68P05 PDFBibTeX XMLCite \textit{S. Dantas} et al., Discrete Math. 306, No. 19--20, 2438--2449 (2006; Zbl 1178.68640) Full Text: DOI
Agnarsson, Geir; Chen, Li On the extension of vertex maps to graph homomorphisms. (English) Zbl 1100.05098 Discrete Math. 306, No. 17, 2021-2030 (2006). MSC: 05C99 PDFBibTeX XMLCite \textit{G. Agnarsson} and \textit{L. Chen}, Discrete Math. 306, No. 17, 2021--2030 (2006; Zbl 1100.05098) Full Text: DOI
Brewster, Richard C.; MacGillivray, Gary Building blocks for the variety of absolute retracts. (English) Zbl 1098.05071 Discrete Math. 306, No. 15, 1758-1764 (2006). MSC: 05C78 PDFBibTeX XMLCite \textit{R. C. Brewster} and \textit{G. MacGillivray}, Discrete Math. 306, No. 15, 1758--1764 (2006; Zbl 1098.05071) Full Text: DOI
Vikas, Narayan A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results. (English) Zbl 1101.68613 J. Comput. Syst. Sci. 71, No. 4, 406-439 (2005). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{N. Vikas}, J. Comput. Syst. Sci. 71, No. 4, 406--439 (2005; Zbl 1101.68613) Full Text: DOI
Dantas, Simone; de Figueiredo, Celina M. H.; Gravier, Sylvain; Klein, Sulamita Finding \(H\)-partitions efficiently. (English) Zbl 1063.05124 Theor. Inform. Appl. 39, No. 1, 133-144 (2005). Reviewer: Haiko Müller (Leeds) MSC: 05C85 68Q25 68R10 PDFBibTeX XMLCite \textit{S. Dantas} et al., Theor. Inform. Appl. 39, No. 1, 133--144 (2005; Zbl 1063.05124) Full Text: DOI Numdam EuDML
Díaz, Josep; Serna, Maria; Thilikos, Dimitrios M. The restrictive \(H\)-coloring problem. (English) Zbl 1062.05055 Discrete Appl. Math. 145, No. 2, 297-305 (2005). Reviewer: Ján Plesník (Bratislava) MSC: 05C15 68R10 68Q17 PDFBibTeX XMLCite \textit{J. Díaz} et al., Discrete Appl. Math. 145, No. 2, 297--305 (2005; Zbl 1062.05055) Full Text: DOI
Feder, Tomás; Madelaine, Florent; Stewart, Iain A. Dichotomies for classes of homomorphism problems involving unary functions. (English) Zbl 1070.68133 Theor. Comput. Sci. 314, No. 1-2, 1-43 (2004). MSC: 68T20 PDFBibTeX XMLCite \textit{T. Feder} et al., Theor. Comput. Sci. 314, No. 1--2, 1--43 (2004; Zbl 1070.68133) Full Text: DOI Link
Vikas, Narayan Computational complexity of compaction to irreflexive cycles. (English) Zbl 1069.68053 J. Comput. Syst. Sci. 68, No. 3, 473-496 (2004). MSC: 68Q17 05C15 05C38 68R10 PDFBibTeX XMLCite \textit{N. Vikas}, J. Comput. Syst. Sci. 68, No. 3, 473--496 (2004; Zbl 1069.68053) Full Text: DOI
Puricella, Antonio; Stewart, Iain A. Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy. (English) Zbl 1044.68163 Theor. Comput. Sci. 290, No. 3, 1897-1913 (2003). MSC: 68W05 68R10 PDFBibTeX XMLCite \textit{A. Puricella} and \textit{I. A. Stewart}, Theor. Comput. Sci. 290, No. 3, 1897--1913 (2003; Zbl 1044.68163) Full Text: DOI
Seif, Steve; Szabó, Csaba Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem. (English) Zbl 1012.68185 J. Complexity 19, No. 2, 153-160 (2003). MSC: 68T20 PDFBibTeX XMLCite \textit{S. Seif} and \textit{C. Szabó}, J. Complexity 19, No. 2, 153--160 (2003; Zbl 1012.68185) Full Text: DOI
Díaz, Josep; Serna, Maria; Thilikos, Dimitrios M. Counting \(H-\)colorings of partial \(k-\)trees. (English) Zbl 0996.68132 Theor. Comput. Sci. 281, No. 1-2, 291-309 (2002). MSC: 68R10 PDFBibTeX XMLCite \textit{J. Díaz} et al., Theor. Comput. Sci. 281, No. 1--2, 291--309 (2002; Zbl 0996.68132) Full Text: DOI
Büki, Judit; Szabó, Csaba Complexity of homomorphisms to direct products of graphs. (English) Zbl 1032.68084 Inf. Process. Lett. 81, No. 4, 175-178 (2002). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{J. Büki} and \textit{C. Szabó}, Inf. Process. Lett. 81, No. 4, 175--178 (2002; Zbl 1032.68084) Full Text: DOI
Feder, T. Fanout limitations on constraint systems. (English) Zbl 0973.68073 Theor. Comput. Sci. 255, No. 1-2, 281-293 (2001). MSC: 68Q15 PDFBibTeX XMLCite \textit{T. Feder}, Theor. Comput. Sci. 255, No. 1--2, 281--293 (2001; Zbl 0973.68073) Full Text: DOI
Hell, Pavol; Nešetřil, Jaroslav; Zhu, Xuding Complexity of tree homomorphisms. (English) Zbl 0868.05018 Discrete Appl. Math. 70, No. 1, 23-36 (1996). Reviewer: P.Kirschenhofer (Leoben) MSC: 05C05 68R10 05C15 05C38 PDFBibTeX XMLCite \textit{P. Hell} et al., Discrete Appl. Math. 70, No. 1, 23--36 (1996; Zbl 0868.05018) Full Text: DOI Link