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
Chawin, Dror; Haviv, Ishay Improved NP-hardness of approximation for orthogonality dimension and minrank. (English) Zbl 1527.05060 SIAM J. Discrete Math. 37, No. 4, 2670-2688 (2023). MSC: 05C15 05C20 03D15 05C50 68Q25 PDFBibTeX XMLCite \textit{D. Chawin} and \textit{I. Haviv}, SIAM J. Discrete Math. 37, No. 4, 2670--2688 (2023; Zbl 1527.05060) Full Text: DOI arXiv
Kratochvíl, Jan Graph covers: where topology meets computer science, and simple means difficult. (English) Zbl 07770276 Lin, Chun-Cheng (ed.) et al., WALCOM: algorithms and computation. 17th international conference and workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13973, 3-11 (2023). MSC: 68Wxx PDFBibTeX XMLCite \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 13973, 3--11 (2023; Zbl 07770276) Full Text: DOI
Sokolov, Georgy Chromatic number of a line with geometric progressions of forbidden distances and the complexity of recognizing distance graphs. (English) Zbl 1521.05048 Mosc. J. Comb. Number Theory 12, No. 3, 247-258 (2023). MSC: 05C15 68Q17 05D10 PDFBibTeX XMLCite \textit{G. Sokolov}, Mosc. J. Comb. Number Theory 12, No. 3, 247--258 (2023; Zbl 1521.05048) Full Text: DOI
Bodirsky, Manuel; Bulín, Jakub; Starke, Florian; Wernthaler, Michael The smallest hard trees. (English) Zbl 1521.05019 Constraints 28, No. 2, 105-137 (2023). MSC: 05C05 05C60 68Q17 68Q25 PDFBibTeX XMLCite \textit{M. Bodirsky} et al., Constraints 28, No. 2, 105--137 (2023; Zbl 1521.05019) Full Text: DOI arXiv
Takhanov, Rustem Computing a partition function of a generalized pattern-based energy over a semiring. (English) Zbl 07729117 Theory Comput. Syst. 67, No. 4, 760-784 (2023). MSC: 68Qxx 68Txx 08Axx PDFBibTeX XMLCite \textit{R. Takhanov}, Theory Comput. Syst. 67, No. 4, 760--784 (2023; Zbl 07729117) Full Text: DOI arXiv
Gasarch, William; Laskowski, Michael; Zhu, Shaopeng \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP’s. (English) Zbl 07722839 Du, Ding-Zhu (ed.) et al., Theory and applications of models of computation. 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13571, 155-175 (2023). MSC: 68Qxx PDFBibTeX XMLCite \textit{W. Gasarch} et al., Lect. Notes Comput. Sci. 13571, 155--175 (2023; Zbl 07722839) 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
Krokhin, Andrei; Opršal, Jakub; Wrochna, Marcin; Živný, Stanislav Topology and adjunction in promise constraint satisfaction. (English) Zbl 07672224 SIAM J. Comput. 52, No. 1, 38-79 (2023). MSC: 68Q17 68Q25 68R05 05C15 PDFBibTeX XMLCite \textit{A. Krokhin} et al., SIAM J. Comput. 52, No. 1, 38--79 (2023; Zbl 07672224) Full Text: DOI arXiv
Ciardo, Lorenzo; Živný, Stanislav CLAP: a new algorithm for promise CSPs. (English) Zbl 07672223 SIAM J. Comput. 52, No. 1, 1-37 (2023). MSC: 68Q25 68R01 90C05 PDFBibTeX XMLCite \textit{L. Ciardo} and \textit{S. Živný}, SIAM J. Comput. 52, No. 1, 1--37 (2023; Zbl 07672223) Full Text: DOI arXiv
Barkowsky, Matthias; Giese, Holger Host-graph-sensitive RETE nets for incremental graph pattern matching with nested graph conditions. (English) Zbl 1512.68064 J. Log. Algebr. Methods Program. 131, Article ID 100841, 25 p. (2023). MSC: 68P05 68Q42 68R10 PDFBibTeX XMLCite \textit{M. Barkowsky} and \textit{H. Giese}, J. Log. Algebr. Methods Program. 131, Article ID 100841, 25 p. (2023; Zbl 1512.68064) 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
Bok, Jan; Brewster, Richard C.; Hell, Pavol; Jedličková, Nikola; Rafiey, Arash Min orderings and list homomorphism dichotomies for signed and unsigned graphs. (English) Zbl 07719364 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, 510-526 (2022). MSC: 68Qxx 68Rxx 68Wxx PDFBibTeX XMLCite \textit{J. Bok} et al., Lect. Notes Comput. Sci. 13568, 510--526 (2022; Zbl 07719364) Full Text: DOI arXiv
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
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
Brandts, Alex; Živný, Stanislav Beyond PCSP (1-in-3, NAE). (English) Zbl 07629147 Inf. Comput. 289, Part A, Article ID 104954, 14 p. (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Brandts} and \textit{S. Živný}, Inf. Comput. 289, Part A, Article ID 104954, 14 p. (2022; Zbl 07629147) Full Text: DOI
Kazda, Alexandr; Mayr, Peter; Zhuk, Dmitriy Small promise CSPs that reduce to large CSPs. (English) Zbl 07596573 Log. Methods Comput. Sci. 18, No. 3, Paper No. 25, 14 p. (2022). MSC: 03B70 68-XX PDFBibTeX XMLCite \textit{A. Kazda} et al., Log. Methods Comput. Sci. 18, No. 3, Paper No. 25, 14 p. (2022; Zbl 07596573) Full Text: DOI arXiv
Foucaud, Florent; Hocquard, Hervé; Lajou, Dimitri; Mitsou, Valia; Pierron, Théo Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity. (English) Zbl 07517132 Algorithmica 84, No. 5, 1183-1212 (2022). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{F. Foucaud} et al., Algorithmica 84, No. 5, 1183--1212 (2022; Zbl 07517132) Full Text: DOI arXiv
Eagles, Nancy Mae; Foley, Angèle M.; Huang, Alice; Karangozishvili, Elene; Yu, Annan \(H\)-chromatic symmetric functions. (English) Zbl 1489.05155 Electron. J. Comb. 29, No. 1, Research Paper P1.28, 39 p. (2022). Reviewer: Arthur L. B. Yang (Tianjin) MSC: 05E05 PDFBibTeX XMLCite \textit{N. M. Eagles} et al., Electron. J. Comb. 29, No. 1, Research Paper P1.28, 39 p. (2022; Zbl 1489.05155) Full Text: DOI arXiv
Naserasr, Reza; Pham, Lan Anh; Wang, Zhouningxin Density of \(C_{-4}\)-critical signed graphs. (English) Zbl 1481.05086 J. Comb. Theory, Ser. B 153, 81-104 (2022). MSC: 05C42 05C22 PDFBibTeX XMLCite \textit{R. Naserasr} et al., J. Comb. Theory, Ser. B 153, 81--104 (2022; Zbl 1481.05086) Full Text: DOI arXiv
Brakensiek, Joshua; Guruswami, Venkatesan Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy. (English) Zbl 1494.68094 SIAM J. Comput. 50, No. 6, 1663-1700 (2021). MSC: 68Q25 08A70 68R07 68W25 PDFBibTeX XMLCite \textit{J. Brakensiek} and \textit{V. Guruswami}, SIAM J. Comput. 50, No. 6, 1663--1700 (2021; Zbl 1494.68094) Full Text: DOI arXiv
Vortmeier, Nils; Kokkinis, Ioannis The dynamic complexity of acyclic hypergraph homomorphisms. (English) Zbl 07538580 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, 232-244 (2021). MSC: 68R10 PDFBibTeX XMLCite \textit{N. Vortmeier} and \textit{I. Kokkinis}, Lect. Notes Comput. Sci. 12911, 232--244 (2021; Zbl 07538580) Full Text: DOI arXiv
Barkowsky, Matthias; Giese, Holger Host-graph-sensitive RETE nets for incremental graph pattern matching. (English) Zbl 1512.68063 Gadducci, Fabio (ed.) et al., Graph transformation. 14th international conference, ICGT 2021, held as part of STAF 2021, virtual event, June 24–25, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12741, 145-163 (2021). MSC: 68P05 68Q42 68R10 PDFBibTeX XMLCite \textit{M. Barkowsky} and \textit{H. Giese}, Lect. Notes Comput. Sci. 12741, 145--163 (2021; Zbl 1512.68063) Full Text: DOI
Hell, Pavol; Nešetřil, Jaroslav In praise of homomorphisms. (English) Zbl 1506.08001 Comput. Sci. Rev. 40, Article ID 100352, 5 p. (2021). MSC: 08A05 08-03 PDFBibTeX XMLCite \textit{P. Hell} and \textit{J. Nešetřil}, Comput. Sci. Rev. 40, Article ID 100352, 5 p. (2021; Zbl 1506.08001) 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
Dallard, Clément; Milanič, Martin; Štorgel, Kenny Treewidth versus clique number. I: Graph classes with a forbidden structure. (English) Zbl 1479.05308 SIAM J. Discrete Math. 35, No. 4, 2618-2646 (2021). MSC: 05C75 05C05 05C69 05C83 05C40 05C85 68P05 PDFBibTeX XMLCite \textit{C. Dallard} et al., SIAM J. Discrete Math. 35, No. 4, 2618--2646 (2021; Zbl 1479.05308) Full Text: DOI arXiv
Groot Koerkamp, Ragnar; Živný, Stanislav On rainbow-free colourings of uniform hypergraphs. (English) Zbl 1517.05127 Theor. Comput. Sci. 885, 69-76 (2021). MSC: 05C65 05C15 05C80 PDFBibTeX XMLCite \textit{R. Groot Koerkamp} and \textit{S. Živný}, Theor. Comput. Sci. 885, 69--76 (2021; Zbl 1517.05127) 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
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
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji Dichotomy for Holant\(^\ast\) problems on the Boolean domain. (English) Zbl 1503.68199 Theory Comput. Syst. 64, No. 8, 1362-1391 (2020). MSC: 68R05 68Q17 68Q25 68R07 68R10 68W05 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., Theory Comput. Syst. 64, No. 8, 1362--1391 (2020; Zbl 1503.68199) Full Text: DOI Link
Matl, Gregor; Živný, Stanislav Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs. (English) Zbl 1494.68202 Algorithmica 82, No. 12, 3492-3520 (2020). MSC: 68R10 68R07 PDFBibTeX XMLCite \textit{G. Matl} and \textit{S. Živný}, Algorithmica 82, No. 12, 3492--3520 (2020; Zbl 1494.68202) Full Text: DOI arXiv
Dross, François; Foucaud, Florent; Mitsou, Valia; Ochem, Pascal; Pierron, Théo Complexity of planar signed graph homomorphisms to cycles. (English) Zbl 1443.05084 Discrete Appl. Math. 284, 166-178 (2020). MSC: 05C22 05C38 05C60 68Q17 PDFBibTeX XMLCite \textit{F. Dross} et al., Discrete Appl. Math. 284, 166--178 (2020; Zbl 1443.05084) Full Text: DOI arXiv
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
Olšák, Miroslav Loop conditions for strongly connected digraphs. (English) Zbl 1454.08006 Int. J. Algebra Comput. 30, No. 3, 467-499 (2020). MSC: 08B05 05C20 05C25 08B20 08A70 PDFBibTeX XMLCite \textit{M. Olšák}, Int. J. Algebra Comput. 30, No. 3, 467--499 (2020; Zbl 1454.08006) Full Text: DOI
Bodirsky, Manuel; Vucaj, Albert Two-element structures modulo primitive positive constructability. (English) Zbl 1477.08003 Algebra Univers. 81, No. 2, Paper No. 20, 17 p. (2020). MSC: 08A40 08A70 08B05 68Q17 PDFBibTeX XMLCite \textit{M. Bodirsky} and \textit{A. Vucaj}, Algebra Univers. 81, No. 2, Paper No. 20, 17 p. (2020; Zbl 1477.08003) Full Text: DOI arXiv
Barto, Libor; Pinsker, Michael Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems). (English) Zbl 1432.68169 SIAM J. Comput. 49, No. 2, 365-393 (2020). MSC: 68Q25 03C05 03C35 08A70 68Q17 68Q27 68R07 PDFBibTeX XMLCite \textit{L. Barto} and \textit{M. Pinsker}, SIAM J. Comput. 49, No. 2, 365--393 (2020; Zbl 1432.68169) Full Text: DOI arXiv
Olšák, Miroslav The local loop lemma. (English) Zbl 1458.08005 Algebra Univers. 81, No. 2, Paper No. 14, 23 p. (2020). Reviewer: Ivan Chajda (Přerov) MSC: 08B20 08B05 05C20 05C25 PDFBibTeX XMLCite \textit{M. Olšák}, Algebra Univers. 81, No. 2, Paper No. 14, 23 p. (2020; Zbl 1458.08005) Full Text: DOI arXiv
Wrochna, Marcin Homomorphism reconfiguration via homotopy. (English) Zbl 1448.68249 SIAM J. Discrete Math. 34, No. 1, 328-350 (2020). MSC: 68Q25 05C15 05E45 68Q17 PDFBibTeX XMLCite \textit{M. Wrochna}, SIAM J. Discrete Math. 34, No. 1, 328--350 (2020; Zbl 1448.68249) Full Text: DOI
Bringmann, Karl; Fischer, Nick; Künnemann, Marvin A fine-grained analogue of Schaefer’s theorem in P: dichotomy of \(\exists^k-\forall\)-quantified first-order graph properties. (English) Zbl 07564431 Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 31, 27 p. (2019). MSC: 68Q25 PDFBibTeX XMLCite \textit{K. Bringmann} et al., LIPIcs -- Leibniz Int. Proc. Inform. 137, Article 31, 27 p. (2019; Zbl 07564431) Full Text: DOI
Bulatov, Andrei A.; Živný, Stanislav Approximate counting CSP seen from the other side. (English) Zbl 1499.68238 Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 60, 14 p. (2019). MSC: 68R07 08A70 68Q25 68Q27 PDFBibTeX XMLCite \textit{A. A. Bulatov} and \textit{S. Živný}, LIPIcs -- Leibniz Int. Proc. Inform. 138, Article 60, 14 p. (2019; Zbl 1499.68238) Full Text: DOI arXiv
Kazeminia, Amirhossein; Bulatov, Andrei A. Counting homomorphisms modulo a prime number. (English) Zbl 07561703 Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 59, 13 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Kazeminia} and \textit{A. A. Bulatov}, LIPIcs -- Leibniz Int. Proc. Inform. 138, Article 59, 13 p. (2019; Zbl 07561703) Full Text: DOI arXiv
Rafiey, Akbar; Rafiey, Arash; Santos, Thiago Toward a dichotomy for approximation of \(H\)-coloring. (English) Zbl 07561584 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 91, 16 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{A. Rafiey} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 91, 16 p. (2019; Zbl 07561584) Full Text: DOI arXiv
Matl, Gregor; Živný, Stanislav Beyond Boolean surjective VCSPs. (English) Zbl 07559161 Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 52, 15 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{G. Matl} and \textit{S. Živný}, LIPIcs -- Leibniz Int. Proc. Inform. 126, Article 52, 15 p. (2019; Zbl 07559161) 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 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
Wrochna, Marcin On inverse powers of graphs and topological implications of Hedetniemi’s conjecture. (English) Zbl 1428.05259 J. Comb. Theory, Ser. B 139, 267-295 (2019). MSC: 05C76 05C99 05C15 PDFBibTeX XMLCite \textit{M. Wrochna}, J. Comb. Theory, Ser. B 139, 267--295 (2019; Zbl 1428.05259) Full Text: DOI arXiv
Jansen, Bart M. P.; Pieterse, Astrid Optimal data reduction for graph coloring using low-degree polynomials. (English) Zbl 1430.68128 Algorithmica 81, No. 10, 3865-3889 (2019). MSC: 68Q27 05C15 05C85 PDFBibTeX XMLCite \textit{B. M. P. Jansen} and \textit{A. Pieterse}, Algorithmica 81, No. 10, 3865--3889 (2019; Zbl 1430.68128) Full Text: DOI arXiv
Groenland, Carla; Okrasa, Karolina; Rzążewski, Paweł; Scott, Alex; Seymour, Paul; Spirkl, Sophie \(H\)-colouring \(P_t\)-free graphs in subexponential time. (English) Zbl 1419.05074 Discrete Appl. Math. 267, 184-189 (2019). MSC: 05C15 05C85 05A15 PDFBibTeX XMLCite \textit{C. Groenland} et al., Discrete Appl. Math. 267, 184--189 (2019; Zbl 1419.05074) Full Text: DOI arXiv
Behrisch, Mike; Vargas-García, Edith; Zhuk, Dmitriy The number of clones determined by disjunctions of unary relations. (English) Zbl 1484.08003 Theory Comput. Syst. 63, No. 6, 1298-1313 (2019). MSC: 08A40 03B50 08A02 68Q25 PDFBibTeX XMLCite \textit{M. Behrisch} et al., Theory Comput. Syst. 63, No. 6, 1298--1313 (2019; Zbl 1484.08003) Full Text: DOI arXiv
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
Cai, Jin-Yi; Chen, Xi A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. (English) Zbl 1429.68079 Comput. Complexity 28, No. 3, 345-408 (2019). MSC: 68Q25 05C20 05C60 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{X. Chen}, Comput. Complexity 28, No. 3, 345--408 (2019; Zbl 1429.68079) 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
Godsil, Chris; Roberson, David E.; Rooney, Brendan; Šámal, Robert; Varvitsiotis, Antonios Graph homomorphisms via vector colorings. (English) Zbl 1414.05199 Eur. J. Comb. 79, 244-261 (2019). MSC: 05C60 05C15 90C22 PDFBibTeX XMLCite \textit{C. Godsil} et al., Eur. J. Comb. 79, 244--261 (2019; Zbl 1414.05199) Full Text: DOI arXiv Link
Kamiński, Marcin; Pstrucha, Anna Certifying coloring algorithms for graphs without long induced paths. (English) Zbl 1410.05204 Discrete Appl. Math. 261, 258-267 (2019). MSC: 05C85 05C15 PDFBibTeX XMLCite \textit{M. Kamiński} and \textit{A. Pstrucha}, Discrete Appl. Math. 261, 258--267 (2019; Zbl 1410.05204) Full Text: DOI arXiv
Duffy, Christopher; MacGillivray, Gary; Ochem, Pascal; Raspaud, André Oriented incidence colourings of digraphs. (English) Zbl 1401.05109 Discuss. Math., Graph Theory 39, No. 1, 191-210 (2019). MSC: 05C15 05C20 PDFBibTeX XMLCite \textit{C. Duffy} et al., Discuss. Math., Graph Theory 39, No. 1, 191--210 (2019; Zbl 1401.05109) Full Text: DOI
Göbel, Andreas; Lagodzinski, J. A. Gregor; Seidel, Karen Counting homomorphisms to trees modulo a prime. (English) Zbl 1495.68174 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 49, 13 p. (2018). MSC: 68R10 05C30 05C60 68Q25 PDFBibTeX XMLCite \textit{A. Göbel} et al., LIPIcs -- Leibniz Int. Proc. Inform. 117, Article 49, 13 p. (2018; Zbl 1495.68174) Full Text: DOI arXiv
Alishahi, Meysam; Taherkhani, Ali Circular chromatic number of induced subgraphs of Kneser graphs. (English) Zbl 1414.05106 Ars Math. Contemp. 15, No. 1, 161-172 (2018). Reviewer: Nader Jafari Rad (Tehran) MSC: 05C15 PDFBibTeX XMLCite \textit{M. Alishahi} and \textit{A. Taherkhani}, Ars Math. Contemp. 15, No. 1, 161--172 (2018; Zbl 1414.05106) 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
Ham, Lucy; Jackson, Marcel Axiomatisability and hardness for universal Horn classes of hypergraphs. (English) Zbl 1522.08003 Algebra Univers. 79, No. 2, Paper No. 30, 17 p. (2018). MSC: 08C15 05C65 05C60 68Q17 03C13 PDFBibTeX XMLCite \textit{L. Ham} and \textit{M. Jackson}, Algebra Univers. 79, No. 2, Paper No. 30, 17 p. (2018; Zbl 1522.08003) Full Text: DOI arXiv
Mahajan, Meena; Saurabh, Nitin Some complete and intermediate polynomials in algebraic complexity theory. (English) Zbl 1393.68079 Theory Comput. Syst. 62, No. 3, 622-652 (2018). MSC: 68Q25 13P25 68Q15 68Q17 PDFBibTeX XMLCite \textit{M. Mahajan} and \textit{N. Saurabh}, Theory Comput. Syst. 62, No. 3, 622--652 (2018; Zbl 1393.68079) Full Text: DOI arXiv
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
Cockburn, Sally Homomorphic preimages of geometric paths. (English) Zbl 1390.05147 Discuss. Math., Graph Theory 38, No. 2, 553-571 (2018). MSC: 05C60 05C62 05C38 PDFBibTeX XMLCite \textit{S. Cockburn}, Discuss. Math., Graph Theory 38, No. 2, 553--571 (2018; Zbl 1390.05147) Full Text: DOI
Cai, Jin-Yi; Guo, Heng; Williams, Tyson Holographic algorithms beyond matchgates. (English) Zbl 1390.68338 Inf. Comput. 259, Part 1, 102-129 (2018). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., Inf. Comput. 259, Part 1, 102--129 (2018; Zbl 1390.68338) Full Text: DOI arXiv
Foniok, Jan; Tardif, Claude Hedetniemi’s conjecture and adjoint functors in thin categories. (English) Zbl 1431.05067 Appl. Categ. Struct. 26, No. 1, 113-128 (2018). MSC: 05C15 05C76 18B35 PDFBibTeX XMLCite \textit{J. Foniok} and \textit{C. Tardif}, Appl. Categ. Struct. 26, No. 1, 113--128 (2018; Zbl 1431.05067) Full Text: DOI arXiv
Bulín, Jakub On the complexity of \(\mathbb{H}\)-coloring for special oriented trees. (English) Zbl 1376.05049 Eur. J. Comb. 69, 54-75 (2018). MSC: 05C15 05C05 05C20 PDFBibTeX XMLCite \textit{J. Bulín}, Eur. J. Comb. 69, 54--75 (2018; Zbl 1376.05049) Full Text: DOI arXiv
Wrochna, Marcin Reconfiguration in bounded bandwidth and tree-depth. (English) Zbl 1382.68183 J. Comput. Syst. Sci. 93, 1-10 (2018). MSC: 68R10 68Q17 68Q25 PDFBibTeX XMLCite \textit{M. Wrochna}, J. Comput. Syst. Sci. 93, 1--10 (2018; Zbl 1382.68183) Full Text: DOI arXiv
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
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; Kozik, Marcin Absorption in universal algebra and CSP. (English) Zbl 1482.68160 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, 45-77 (2017). MSC: 68R07 08A70 68Q25 PDFBibTeX XMLCite \textit{L. Barto} and \textit{M. Kozik}, Dagstuhl Follow-Ups 7, 45--77 (2017; Zbl 1482.68160) 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
Takhanov, Rustem Hybrid VCSPs with crisp and valued conservative templates. (English) Zbl 1457.68130 Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 65, 13 p. (2017). MSC: 68Q25 08A02 08A70 68R07 PDFBibTeX XMLCite \textit{R. Takhanov}, LIPIcs -- Leibniz Int. Proc. Inform. 92, Article 65, 13 p. (2017; Zbl 1457.68130) Full Text: DOI
Bonamy, Marthe; Kowalik, Łukasz; Pilipczuk, Michał; Socała, Arkadiusz; Wrochna, Marcin Tight lower bounds for the complexity of multicoloring. (English) Zbl 1434.68186 Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 18, 14 p. (2017). MSC: 68Q17 05C15 05C60 PDFBibTeX XMLCite \textit{M. Bonamy} et al., LIPIcs -- Leibniz Int. Proc. Inform. 87, Article 18, 14 p. (2017; Zbl 1434.68186) Full Text: DOI arXiv
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
Tikhomirov, Mikhail On complexity of multidistance graph recognition in \(\mathbb{R}^1\). (English) Zbl 1378.05088 Drmota, Michael (ed.) et al., Extended abstracts of the ninth European conference on combinatorics, graph theory and applications, EuroComb 2017, Vienna, Austria, August 28 – September 1, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 61, 1039-1045 (2017). MSC: 05C25 05C10 05C60 68Q17 PDFBibTeX XMLCite \textit{M. Tikhomirov}, Electron. Notes Discrete Math. 61, 1039--1045 (2017; Zbl 1378.05088) Full Text: DOI arXiv
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
Cohen, David A.; Cooper, Martin C.; Jeavons, Peter G.; Krokhin, Andrei; Powell, Robert; Živný, Stanislav Binarisation for valued constraint satisfaction problems. (English) Zbl 1477.68121 SIAM J. Discrete Math. 31, No. 4, 2279-2300 (2017). MSC: 68Q25 08A70 68Q17 PDFBibTeX XMLCite \textit{D. A. Cohen} et al., SIAM J. Discrete Math. 31, No. 4, 2279--2300 (2017; Zbl 1477.68121) Full Text: DOI arXiv
Hamilton, Kathleen E.; Humble, Travis S. Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets. (English) Zbl 1373.81139 Quantum Inf. Process. 16, No. 4, Paper No. 94, 17 p. (2017). MSC: 81P68 05C90 90C59 PDFBibTeX XMLCite \textit{K. E. Hamilton} and \textit{T. S. Humble}, Quantum Inf. Process. 16, No. 4, Paper No. 94, 17 p. (2017; Zbl 1373.81139) Full Text: DOI arXiv
Bensmail, Julien; Duffy, Christopher; Sen, Sagnik Analogues of cliques for \((m,n)\)-colored mixed graphs. (English) Zbl 1371.05071 Graphs Comb. 33, No. 4, 735-750 (2017). MSC: 05C15 05C69 05C60 05C10 PDFBibTeX XMLCite \textit{J. Bensmail} et al., Graphs Comb. 33, No. 4, 735--750 (2017; Zbl 1371.05071) Full Text: DOI HAL
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
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
Đ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
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
Ochem, Pascal; Movarraei, Nazanin Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms. (English) Zbl 1405.05120 Inf. Process. Lett. 123, 42-46 (2017). MSC: 05C60 05C15 68Q25 PDFBibTeX XMLCite \textit{P. Ochem} and \textit{N. Movarraei}, Inf. Process. Lett. 123, 42--46 (2017; Zbl 1405.05120) 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
Brewster, Richard C.; Foucaud, Florent; Hell, Pavol; Naserasr, Reza The complexity of signed graph and edge-coloured graph homomorphisms. (English) Zbl 1351.05099 Discrete Math. 340, No. 2, 223-235 (2017). MSC: 05C22 05C15 05C60 PDFBibTeX XMLCite \textit{R. C. Brewster} et al., Discrete Math. 340, No. 2, 223--235 (2017; Zbl 1351.05099) Full Text: DOI arXiv
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan Nonnegative weighted #CSP: an effective complexity dichotomy. (English) Zbl 1356.68094 SIAM J. Comput. 45, No. 6, 2177-2198 (2016). MSC: 68Q25 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., SIAM J. Comput. 45, No. 6, 2177--2198 (2016; Zbl 1356.68094) Full Text: DOI arXiv
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
Tikhomirov, M. I. On the distance and multidistance graph embeddability problem. (English. Russian original) Zbl 1348.05069 Dokl. Math. 93, No. 3, 280-281 (2016); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 468, No. 3, 261-263 (2016). MSC: 05C12 05C60 PDFBibTeX XMLCite \textit{M. I. Tikhomirov}, Dokl. Math. 93, No. 3, 280--281 (2016; Zbl 1348.05069); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 468, No. 3, 261--263 (2016) Full Text: DOI
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
Kowalczyk, Michael; Cai, Jin-Yi Holant problems for 3-regular graphs with complex edge functions. (English) Zbl 1350.68151 Theory Comput. Syst. 59, No. 1, 133-158 (2016). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{M. Kowalczyk} and \textit{J.-Y. Cai}, Theory Comput. Syst. 59, No. 1, 133--158 (2016; Zbl 1350.68151) Full Text: DOI Link
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
Cai, Jin-Yi; Guo, Heng; Williams, Tyson A complete dichotomy rises from the capture of vanishing signatures. (English) Zbl 1350.68133 SIAM J. Comput. 45, No. 5, 1671-1728 (2016). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., SIAM J. Comput. 45, No. 5, 1671--1728 (2016; Zbl 1350.68133) Full Text: DOI arXiv
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
Miracle, Sarah; Randall, Dana Algorithms to approximately count and sample conforming colorings of graphs. (English) Zbl 1339.05142 Discrete Appl. Math. 210, 133-149 (2016). MSC: 05C15 05C69 60J10 65C05 PDFBibTeX XMLCite \textit{S. Miracle} and \textit{D. Randall}, Discrete Appl. Math. 210, 133--149 (2016; Zbl 1339.05142) Full Text: DOI
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark Approximately counting \(H\)-colorings is \(\#\)BIS-hard. (English) Zbl 1342.68147 SIAM J. Comput. 45, No. 3, 680-711 (2016). MSC: 68Q17 05C15 05C30 05C69 68W20 68W25 PDFBibTeX XMLCite \textit{A. Galanis} et al., SIAM J. Comput. 45, No. 3, 680--711 (2016; Zbl 1342.68147) Full Text: DOI