Surjective H-Colouring: New Hardness Results

Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart

Type: Book-Chapter

Publication Date: 2017-01-01

Citations: 5

DOI: https://doi.org/10.1007/978-3-319-58741-7_26

View Publication

Download PDF

Locations

Lecture notes in computer science - View
Durham Research Online (Durham University) - View - PDF
arXiv (Cornell University) - View - PDF
Durham Research Online (Durham University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	2-dipath and proper 2-dipath k-colourings	2011	Kailyn M. Young
+	Complexity of infinite H-colouring	1990	Bruce L. Bauslaugh
+ PDF Chat	Hypergraph colouring and the Lovász Local Lemma	1997	Colin McDiarmid
+	The complexity of G-free colourability	1997	Demetrios Achlioptas
+	k-Colouring when k is close to Δ	2000	Michael Molloy Bruce Reed
+	A counterexample to the Ch(G)-conjecture	2000	Phạm Anh Minh
+	Hardness transitions and uniqueness of acyclic colouring	2023	Shalu M.A. Cyriac Antony
+	Towards a Version of Ohba’s Conjecture for Improper Colorings	2017	Wei Wang Jianguo Qian Zhidan Yan
+	Wheel-Free Deletion Is W[2]-Hard	2008	Daniel Lokshtanov
+	On the complexity of H-coloring	1990	Pavol Hell Jaroslav Nešetřil
+	The Colorful Helly Property for Hypergraphs	2009	Rommel Barbosa Mitre C. Dourado Erika M. Martins Jayme L. Szwarcfiter
+	Injective Colorings with Arithmetic Constraints	2015	Natacha Astromujoff Mathieu Chapelle Martı́n Matamala Ioan Todinca José Zamora
+	A SURVEY ON $K$-FREENESS	2005	Francesco Pappalardi
+	The complexity of generalized colourings	1989	Gary MacGillivray
+	No-hole L(2,1)-colorings	2003	Peter C. Fishburn Fred S. Roberts
+ PDF Chat	A reduction theorem for the McKay conjecture	2007	I. M. Isaacs Gunter Malle Gabriel Navarro
+	Greedy algorithms, H-colourings and a complexity-theoretic dichotomy	2003	Antonio Puricella Iain A. Stewart
+	A note on strong edge-colouring	2012	Hervé Hocquard Mickaël Montassier
+	On Polynomial Kernelization of $$\mathcal {H}$$ H -free Edge Deletion	2016	N. R. Aravind R. B. Sandeep Naveen Sivadasan
+	The complexity of surjective homomorphism problems—a survey	2012	Manuel Bodirsky Jan Kára Barnaby Martin

Works That Cite This (5)

Action	Title	Year	Authors
+	Coloring Problems on Bipartite Graphs of Small Diameter	2020	Víctor Campos Guilherme C. M. Gomes Allen Ibiapina Raul Lopes Ignasi Sau Ana Silva
+ PDF Chat	Surjective H-Colouring over Reflexive Digraphs	2018	Benoît Larose Barnaby Martin Daniël Paulusma
+ PDF Chat	The Complexity of Approximately Counting Retractions	2020	Jacob Focke Leslie Ann Goldberg Stanislav Živný
+	Disconnected Cuts in Claw-free Graphs	2018	Barnaby Martin Daniël Paulusma Erik Jan van Leeuwen
+	Surjective H-Colouring over Reflexive Digraphs	2017	Benoît Larose Barnaby Martin Daniël Paulusma

Works Cited by This (9)

Action	Title	Year	Authors
+ PDF Chat	Locally constrained graph homomorphisms—structure, complexity, and applications	2008	Jiřı́ Fiala Jan Kratochvı́l
+	The complexity of surjective homomorphism problems—a survey	2012	Manuel Bodirsky Jan Kára Barnaby Martin
+	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
+	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
+ PDF Chat	Computing vertex-surjective homomorphisms to partially reflexive trees	2012	Petr A. Golovach Daniël Paulusma Jian Song
+	On the complexity of H-coloring	1990	Pavol Hell Jaroslav Nešetřil
+ PDF Chat	Finding vertex-surjective graph homomorphisms	2012	Petr A. Golovach Bernard Lidický Barnaby Martin Daniël Paulusma
+	Bi‐arc graphs and the complexity of list homomorphisms	2002	Tomás Feder Pavol Hell Jing Huang