Hell, Pavol; Huang, Jing; Lin, Jephian C.-H. Strong cocomparability graphs and slash-free orderings of matrices. (English) Zbl 07809682 SIAM J. Discrete Math. 38, No. 1, 828-844 (2024). MSC: 05C50 05C75 06A07 PDFBibTeX XMLCite \textit{P. Hell} et al., SIAM J. Discrete Math. 38, No. 1, 828--844 (2024; Zbl 07809682) 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
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 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
Safe, Martín D. Essential obstacles to Helly circular-arc graphs. (English) Zbl 1504.05199 Discrete Appl. Math. 320, 245-258 (2022). Reviewer: Brahadeesh Sankarnarayanan (Mumbai) MSC: 05C62 05C75 05C85 PDFBibTeX XMLCite \textit{M. D. Safe}, Discrete Appl. Math. 320, 245--258 (2022; Zbl 1504.05199) 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
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
Hell, Pavol; Huang, Jing; Lin, Jephian C.-H.; McConnell, Ross M. Bipartite analogues of comparability and cocomparability graphs. (English) Zbl 1450.05089 SIAM J. Discrete Math. 34, No. 3, 1969-1983 (2020). MSC: 05C99 05C75 05C85 PDFBibTeX XMLCite \textit{P. Hell} et al., SIAM J. Discrete Math. 34, No. 3, 1969--1983 (2020; Zbl 1450.05089) 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
Okrasa, Karolina; Rzążewski, Paweł Subexponential algorithms for variants of the homomorphism problem in string graphs. (English) Zbl 1435.68243 J. Comput. Syst. Sci. 109, 126-144 (2020). MSC: 68R10 05C60 05C62 05C85 68Q25 PDFBibTeX XMLCite \textit{K. Okrasa} and \textit{P. Rzążewski}, J. Comput. Syst. Sci. 109, 126--144 (2020; Zbl 1435.68243) 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
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
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
Huang, Jing Lexicographic orientation algorithms. (English) Zbl 1407.05112 Bang-Jensen, Jørgen (ed.) et al., Classes of directed graphs. Cham: Springer. Springer Monogr. Math., 575-607 (2018). MSC: 05C20 05C38 05C12 PDFBibTeX XMLCite \textit{J. Huang}, in: Classes of directed graphs. Cham: Springer. 575--607 (2018; Zbl 1407.05112) Full Text: DOI
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
Atminas, Aistis; Zamaraev, Viktor On forbidden induced subgraphs for unit disk graphs. (English) Zbl 1394.05105 Discrete Comput. Geom. 60, No. 1, 57-97 (2018). MSC: 05C75 05C62 05C60 PDFBibTeX XMLCite \textit{A. Atminas} and \textit{V. Zamaraev}, Discrete Comput. Geom. 60, No. 1, 57--97 (2018; Zbl 1394.05105) Full Text: DOI arXiv
Kloks, Ton; Wang, Yue-Li On retracts, absolute retracts, and foldings in cographs. (English) Zbl 1393.05187 Optim. Lett. 12, No. 3, 535-549 (2018). MSC: 05C60 68Q25 PDFBibTeX XMLCite \textit{T. Kloks} and \textit{Y.-L. Wang}, Optim. Lett. 12, No. 3, 535--549 (2018; Zbl 1393.05187) 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
Hartinger, Tatiana Romina; Milanič, Martin Partial characterizations of 1-perfectly orientable graphs. (English) Zbl 1365.05109 J. Graph Theory 85, No. 2, 378-394 (2017). MSC: 05C20 05C75 PDFBibTeX XMLCite \textit{T. R. Hartinger} and \textit{M. Milanič}, J. Graph Theory 85, No. 2, 378--394 (2017; Zbl 1365.05109) Full Text: DOI arXiv
Das, Ashok Kumar; Chakraborty, Ritapa Graphs and digraphs represented by intervals and circular arcs. (English) Zbl 1365.05107 Discrete Appl. Math. 228, 41-49 (2017). MSC: 05C20 PDFBibTeX XMLCite \textit{A. K. Das} and \textit{R. Chakraborty}, Discrete Appl. Math. 228, 41--49 (2017; Zbl 1365.05107) Full Text: DOI
Kim, Eun Jung; Paul, Christophe; Sau, Ignasi; Thilikos, Dimitrios M. Parameterized algorithms for min-max multiway cut and list digraph homomorphism. (English) Zbl 1370.68131 J. Comput. Syst. Sci. 86, 191-206 (2017). MSC: 68Q25 05C85 PDFBibTeX XMLCite \textit{E. J. Kim} et al., J. Comput. Syst. Sci. 86, 191--206 (2017; Zbl 1370.68131) 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
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
Chaplick, Steven; Hell, Pavol; Otachi, Yota; Saitoh, Toshiki; Uehara, Ryuhei Ferrers dimension of grid intersection graphs. (English) Zbl 1350.05142 Discrete Appl. Math. 216, Part 1, 130-135 (2017). MSC: 05C75 05C99 PDFBibTeX XMLCite \textit{S. Chaplick} et al., Discrete Appl. Math. 216, Part 1, 130--135 (2017; Zbl 1350.05142) 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
Mustaţă, Irina; Nishikawa, Kousuke; Takaoka, Asahi; Tayu, Satoshi; Ueno, Shuichi On orthogonal ray trees. (English) Zbl 1329.05274 Discrete Appl. Math. 201, 201-212 (2016). MSC: 05C83 05C05 68R10 68M10 PDFBibTeX XMLCite \textit{I. Mustaţă} et al., Discrete Appl. Math. 201, 201--212 (2016; Zbl 1329.05274) Full Text: DOI
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
Das, Ashok Kumar; Das, Sandip; Sen, Malay Forbidden substructure for interval digraphs/bigraphs. (English) Zbl 1327.05132 Discrete Math. 339, No. 2, 1028-1051 (2016). MSC: 05C20 PDFBibTeX XMLCite \textit{A. K. Das} et al., Discrete Math. 339, No. 2, 1028--1051 (2016; Zbl 1327.05132) Full Text: DOI
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
Adiga, Abhijin; Babu, Jasine; Chandran, L. Sunil A constant factor approximation algorithm for boxicity of circular arc graphs. (English) Zbl 1300.05188 Discrete Appl. Math. 178, 1-18 (2014). MSC: 05C62 68W25 PDFBibTeX XMLCite \textit{A. Adiga} et al., Discrete Appl. Math. 178, 1--18 (2014; Zbl 1300.05188) 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
Golumbic, Martin Charles; Weingarten, Nirit Lefel; Limouzy, Vincent Co-TT graphs and a characterization of split co-TT graphs. (English) Zbl 1408.05112 Discrete Appl. Math. 165, 168-174 (2014). MSC: 05C75 05C62 05C85 68Q25 PDFBibTeX XMLCite \textit{M. C. Golumbic} et al., Discrete Appl. Math. 165, 168--174 (2014; Zbl 1408.05112) Full Text: DOI
Durán, Guillermo; Grippo, Luciano N.; Safe, Martín D. Structural results on circular-arc graphs and circle graphs: a survey and the main open problems. (English) Zbl 1288.05054 Discrete Appl. Math. 164, Part 2, 427-443 (2014). MSC: 05C10 05C75 PDFBibTeX XMLCite \textit{G. Durán} et al., Discrete Appl. Math. 164, Part 2, 427--443 (2014; Zbl 1288.05054) 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
Egri, László; Krokhin, Andrei; Larose, Benoit; Tesson, Pascal The complexity of the list homomorphism problem for graphs. (English) Zbl 1322.68100 Theory Comput. Syst. 51, No. 2, 143-178 (2012). Reviewer: Guillaume Fertin (Nantes) MSC: 68Q25 05C25 05C60 68Q17 PDFBibTeX XMLCite \textit{L. Egri} et al., Theory Comput. Syst. 51, No. 2, 143--178 (2012; Zbl 1322.68100) 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
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
Shrestha, Anish Man Singh; Tayu, Satoshi; Ueno, Shuichi On orthogonal ray graphs. (English) Zbl 1222.05219 Discrete Appl. Math. 158, No. 15, 1650-1659 (2010). MSC: 05C75 PDFBibTeX XMLCite \textit{A. M. S. Shrestha} et al., Discrete Appl. Math. 158, No. 15, 1650--1659 (2010; Zbl 1222.05219) Full Text: DOI
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
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
Gutin, Gregory; Rafiey, Arash; Yeo, Anders Minimum cost homomorphism dichotomy for oriented cycles. (English) Zbl 1188.05073 Graphs Comb. 25, No. 4, 521-531 (2009). Reviewer: Wai-Kai Chen (Fremont) MSC: 05C20 PDFBibTeX XMLCite \textit{G. Gutin} et al., Graphs Comb. 25, No. 4, 521--531 (2009; Zbl 1188.05073) Full Text: DOI
Lin, Min Chih; Szwarcfiter, Jayme L. Characterizations and recognition of circular-arc graphs and subclasses: a survey. (English) Zbl 1228.05218 Discrete Math. 309, No. 18, 5618-5635 (2009). MSC: 05C62 05C38 05C85 05-02 PDFBibTeX XMLCite \textit{M. C. Lin} and \textit{J. L. Szwarcfiter}, Discrete Math. 309, No. 18, 5618--5635 (2009; Zbl 1228.05218) 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
Jonsson, Peter; Nordh, Gustav Introduction to the Maximum Solution problem. (English) Zbl 1171.68499 Creignou, Nadia (ed.) et al., Complexity of constraints. An overview of current research themes. Berlin: Springer (ISBN 978-3-540-92799-0/pbk). Lecture Notes in Computer Science 5250, 255-282 (2008). MSC: 68Q25 68T20 90C27 PDFBibTeX XMLCite \textit{P. Jonsson} and \textit{G. Nordh}, Lect. Notes Comput. Sci. 5250, 255--282 (2008; Zbl 1171.68499) Full Text: DOI
Gutin, Gregory; Rafiey, Arash; Yeo, Anders Minimum cost homomorphism dichotomy for oriented cycles. (English) Zbl 1143.90390 Fleischer, Rudolf (ed.) et al., Algorithmic aspects in information and management. 4th international conference, AAIM 2008, Shanghai, China, June 23–25, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68865-5/pbk). Lecture Notes in Computer Science 5034, 224-234 (2008). MSC: 90C35 PDFBibTeX XMLCite \textit{G. Gutin} et al., Lect. Notes Comput. Sci. 5034, 224--234 (2008; Zbl 1143.90390) 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
Gutin, Gregory; Hell, Pavol; Rafiey, Arash; Yeo, Anders A dichotomy for minimum cost graph homomorphisms. (English) Zbl 1149.90164 Eur. J. Comb. 29, No. 4, 900-911 (2008). Reviewer: Rainer E. Burkard (Graz) MSC: 90C35 PDFBibTeX XMLCite \textit{G. Gutin} et al., Eur. J. Comb. 29, No. 4, 900--911 (2008; Zbl 1149.90164) 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
Huang, Jing Representation characterizations of chordal bipartite graphs. (English) Zbl 1095.05031 J. Comb. Theory, Ser. B 96, No. 5, 673-683 (2006). MSC: 05C75 PDFBibTeX XMLCite \textit{J. Huang}, J. Comb. Theory, Ser. B 96, No. 5, 673--683 (2006; Zbl 1095.05031) Full Text: DOI
Gutin, Gregory; Rafiey, Arash; Yeo, Anders Minimum cost and list homomorphisms to semicomplete digraphs. (English) Zbl 1138.05032 Discrete Appl. Math. 154, No. 6, 890-897 (2006). Reviewer: Wai-Kai Chen (Fremont) MSC: 05C20 05C15 PDFBibTeX XMLCite \textit{G. Gutin} et al., Discrete Appl. Math. 154, No. 6, 890--897 (2006; Zbl 1138.05032) Full Text: DOI
Gutin, Gregory; Rafiey, Arash; Yeo, Anders; Tso, Michael Level of repair analysis and minimum cost homomorphisms of graphs. (English) Zbl 1131.90020 Discrete Appl. Math. 154, No. 6, 881-889 (2006). MSC: 90B25 90B06 05C20 05C69 90C35 PDFBibTeX XMLCite \textit{G. Gutin} et al., Discrete Appl. Math. 154, No. 6, 881--889 (2006; Zbl 1131.90020) Full Text: DOI Link
Feder, Tomás; Hell, Pavol; Klein, Sulamita; Nogueira, Loana Tito; Protti, Fábio List matrix partitions of chordal graphs. (English) Zbl 1084.05026 Theor. Comput. Sci. 349, No. 1, 52-66 (2005). MSC: 05C15 05C70 68Q25 68R10 PDFBibTeX XMLCite \textit{T. Feder} et al., Theor. Comput. Sci. 349, No. 1, 52--66 (2005; Zbl 1084.05026) 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
Hell, Pavol; Huang, Jing A generalization of the theorem of Lekkerkerker and Boland. (English) Zbl 1073.05026 Discrete Math. 299, No. 1-3, 113-119 (2005). MSC: 05C15 05C75 PDFBibTeX XMLCite \textit{P. Hell} and \textit{J. Huang}, Discrete Math. 299, No. 1--3, 113--119 (2005; Zbl 1073.05026) Full Text: DOI
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
Jonsson, Peter; Krokhin, Andrei Recognizing frozen variables in constraint satisfaction problems. (English) Zbl 1086.68056 Theor. Comput. Sci. 329, No. 1-3, 93-113 (2004). MSC: 68Q25 68T20 PDFBibTeX XMLCite \textit{P. Jonsson} and \textit{A. Krokhin}, Theor. Comput. Sci. 329, No. 1--3, 93--113 (2004; Zbl 1086.68056) 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
Feder, Tomas; Hell, Pavol List homomorphisms to reflexive graphs. (English) Zbl 0904.05078 J. Comb. Theory, Ser. B 72, No. 2, 236-250 (1998). Reviewer: P.Hell (Burnaby, BC) MSC: 05C85 68Q25 PDFBibTeX XMLCite \textit{T. Feder} and \textit{P. Hell}, J. Comb. Theory, Ser. B 72, No. 2, 236--250 (1998; Zbl 0904.05078) Full Text: DOI
Hell, Pavol; Huang, Jing Two remarks on circular arc graphs. (English) Zbl 0868.05043 Graphs Comb. 13, No. 1, 65-72 (1997). Reviewer: Ma Zhongfan (Beijing) MSC: 05C75 68R10 PDFBibTeX XMLCite \textit{P. Hell} and \textit{J. Huang}, Graphs Comb. 13, No. 1, 65--72 (1997; Zbl 0868.05043) Full Text: DOI