Computing vertex-surjective homomorphisms to partially reflexive trees

Petr A. Golovach, Daniël Paulusma, Jian Song

Type: Article

Publication Date: 2012-07-10

Citations: 19

DOI: https://doi.org/10.1016/j.tcs.2012.06.039

View Publication

Download PDF

Locations

Durham Research Online (Durham University) - View - PDF
Theoretical Computer Science - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees	2011	Petr A. Golovach Daniël Paulusma Jian Song
+ PDF Chat	Finding vertex-surjective graph homomorphisms	2012	Petr A. Golovach Bernard Lidický Barnaby Martin Daniël Paulusma
+	Finding Vertex-Surjective Graph Homomorphisms	2012	Petr A. Golovach Bernard Lidický Barnaby Martin Daniël Paulusma
+	Surjective H-Colouring: New Hardness Results	2017	Petr A. Golovach Matthew Johnson. Barnaby Martin Daniël Paulusma Anthony Stewart
+	Surjective H-Colouring: New Hardness Results	2017	Petr A. Golovach Matthew Johnson. Barnaby Martin Daniël Paulusma Antony Stewart
+	Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree	2015	Steven Chaplick Jiřı́ Fiala Pim van ’t Hof Daniël Paulusma Marek Tesař
+ PDF Chat	Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree	2013	Steven Chaplick Jiřı́ Fiala Pim van ’t Hof Daniël Paulusma Marek Tesař
+	List Locally Surjective Homomorphisms in Hereditary Graph Classes	2022	Pavel Dvořák Monika Krawczyk Tomáš Masařík Jana Novotná Paweł Rzążewski Aneta Żuk
+ PDF Chat	Surjective H-colouring: New hardness results	2018	Petr A. Golovach Matthew Johnson Barnaby Martin Daniël Paulusma Anthony Stewart
+	Surjective H-Colouring over Reflexive Digraphs	2017	Benoît Larose Barnaby Martin Daniël Paulusma
+	Surjective H-Colouring over Reflexive Digraphs	2017	Benoît Larose Barnaby Martin Daniël Paulusma
+ PDF Chat	Testing List H-homomorphisms	2012	Yuichi Yoshida
+ PDF Chat	Surjective H-Colouring over Reflexive Digraphs	2018	Benoît Larose Barnaby Martin Daniël Paulusma
+	The Complexity of Colouring by Infinite Vertex Transitive Graphs	1993	Bruce L. Bauslaugh
+	Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs	2019	Karolina Okrasa Paweł Rzążewski
+	Testing List H-Homomorphisms	2011	Yuichi Yoshida
+	Full complexity classification of the list homomorphism problem for bounded-treewidth graphs	2020	Karolina Okrasa Marta Piecyk Paweł Rzążewski
+ PDF Chat	Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs	2021	Karolina Okrasa Paweł Rzążewski
+ PDF Chat	The Complexity of Counting Surjective Homomorphisms and Compactions	2018	Jacob Focke Leslie Ann Goldberg Stanislav Živný
+ PDF Chat	The Complexity of Counting Surjective Homomorphisms and Compactions	2019	Jacob Focke Leslie Ann Goldberg Stanislav Živný

Works That Cite This (13)

Action	Title	Year	Authors
+ PDF Chat	Finding Matching Cuts in H-Free Graphs	2023	Felicia Lucke Daniël Paulusma Bernard Ries
+ PDF Chat	Surjective H-Colouring over Reflexive Digraphs	2018	Benoît Larose Barnaby Martin Daniël Paulusma
+	On the complexity of matching cut for graphs of bounded radius and H-free graphs	2022	Felicia Lucke Daniël Paulusma Bernard Ries
+ PDF Chat	The Complexity of Counting Surjective Homomorphisms and Compactions	2019	Jacob Focke Leslie Ann Goldberg Stanislav Živný
+ PDF Chat	The Complexity of Approximately Counting Retractions	2020	Jacob Focke Leslie Ann Goldberg Stanislav Živný
+ PDF Chat	Surjective H-Colouring: New Hardness Results	2017	Petr A. Golovach Matthew Johnson Barnaby Martin Daniël Paulusma Anthony Stewart
+ PDF Chat	No-Rainbow Problem and the Surjective Constraint Satisfaction Problem	2021	Dmitriy Zhuk
+ PDF Chat	QCSP on Reflexive Tournaments	2022	Benoît Larose Barnaby Martin Petar Marković Daniël Paulusma Siani Smith Stanislav Živný
+ PDF Chat	An algebraic hardness criterion for surjective constraint satisfaction	2014	Hubie Chen
+	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius	2024	Felicia Lucke Daniël Paulusma Bernard Ries

Works Cited by This (15)

Action	Title	Year	Authors
+ PDF Chat	Locally constrained graph homomorphisms—structure, complexity, and applications	2008	Jiřı́ Fiala Jan Kratochvı́l
+ PDF Chat	Grad and classes with bounded expansion I. Decompositions	2007	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Computational Complexity of Compaction to Reflexive Cycles	2002	Narayan Vikas
+	A complete complexity classification of the role assignment problem	2005	Jiřı́ Fiala Daniël Paulusma
+ PDF Chat	Grad and classes with bounded expansion III. Restricted graph homomorphism dualities	2008	Jaroslav Nešetřil Patrice Ossona de Mendez
+	A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results	2005	Narayan Vikas
+	Linear time low tree-width partitions and algorithmic consequences	2006	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Grad and classes with bounded expansion II. Algorithmic aspects	2007	Jaroslav Nešetřil Patrice Ossona de Mendez
+	On the complexity of H-coloring	1990	Pavol Hell Jaroslav Nešetřil
+	Covering graphs with few complete bipartite subgraphs	2009	Herbert Fleischner Egbert Mujuni Daniël Paulusma Stefan Szeider