On the complexity of H-coloring

Pavol Hell, Jaroslav Nešetřil

Type: Article

Publication Date: 1990-02-01

Citations: 683

DOI: https://doi.org/10.1016/0095-8956(90)90132-j

View Publication

Locations

Journal of Combinatorial Theory Series B - View

Similar Works

Action	Title	Year	Authors
+	On the complexity of cd-coloring of graphs	2018	Shalu M.A. S. Vijayakumar T. P. Sandhya
+	On a list-coloring problem	2003	Sylvain Gravier Frédéric Maffray Bojan Mohar
+ PDF Chat	The Complexity of Grid Coloring	2022	Daniel Apon William Gasarch Kevin Lawler
+	On the complexity of 4-coloring graphs without long induced paths	2007	Van Bang Lê Bert Randerath Ingo Schiermeyer
+	The complexity of H-colouring of bounded degree graphs	2000	Anna Galluccio Pavol Hell Jaroslav Nešetřil
+	On the Parameterized Complexity of Odd Coloring	2025	Sriram Bhyravarapu Swati Kumari I. Vinod Reddy
+	On Coloring Problems	2013	Weifan Wang Yuehua Bu
+ PDF Chat	On the complexity of graph coloring with additional local conditions	2018	Yaroslav Shitov
+ PDF Chat	The Complexity of the Partition Coloring Problem	2020	Zhenyu Guo Mingyu Xiao Yi Zhou
+ PDF Chat	On Split-Coloring Problems	2005	Tınaz Ekim D. de Werra
+ PDF Chat	Notes on complexity of packing coloring	2018	Minki Kim Bernard Lidický Tomáš Masařík Florian Pfender
+ PDF Chat	On Differences Between DP-Coloring and List Coloring	2019	Anton Bernshteyn Alexandr Kostochka
+ PDF Chat	On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem	2013	Prachi Goyal Vikram Kamat Neeldhara Misra
+	ON THE COLORING PROBLEM OF GRAPHS. I	1956	Tadashi. Hiraoka
+	On the complexity of local-equitable coloring of graphs	2022	Zuosong Liang Juan Wang Junqing Cai Xin Yang
+	On the complexity of the k-independence number and the h-diameter of a graph	2023	Aida Abiad Hidde Koerts
+ PDF Chat	Combinatorial Problems on H-graphs	2017	Steven Chaplick Peter Zeman
+	On a bound of Graham and Spencer for a graph-coloring constant	1973	Robert W. Irving
+	Parameterized Complexity of Coupon Coloring of Graphs	2025	Pradeesha Ashok Pradyun Devarakonda Shiven Phogat Swaroop A. Ram Rayala J. A. Sherin
+	On Coloring Problems of Snark Families	2011	Diana Sasaki Simone Dantas Celina M. H. de Figueiredo

Works That Cite This (448)

Action	Title	Year	Authors
+	Between Colorings and Layouts - Minimum Morphism Cost Problems	2007	Dieter Mitsche
+	Graph homomorphisms via vector colorings	2019	Chris Godsil David E. Roberson Brendan Rooney Robert Šámal Antonios Varvitsiotis
+ PDF Chat	Holographic Algorithms Beyond Matchgates	2014	Jin‐Yi Cai Heng Guo Tyson Williams
+	Retractions onto series-parallel posets	2007	Víctor Dalmau Andrei Krokhin Benoît Larose
+ PDF Chat	List H-Coloring a Graph by Removing Few Vertices	2016	Rajesh Chitnis László Egri Dániel Marx
+ PDF Chat	Complexity of Counting CSP with Complex Weights	2017	Jin‐Yi Cai Xi Chen
+	The Complexity of Partition Functions on Hermitian Matrices	2010	Marc Thurley
+	List Covering of Regular Multigraphs with Semi-edges	2023	Jan Bok Jiřı́ Fiala Nikola Jedličková Jan Kratochvı́l Paweł Rzążewski
+	Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds	2024	Jacob Focke Dániel Marx Paweł Rzążewski
+	Partial covers of graphs	2002	Jiřı́ Fiala Jan Kratochvı́l

Works Cited by This (5)

Action	Title	Year	Authors
+ PDF Chat	The Complexity of Near-Optimal Graph Coloring	1976	M. R. Garey David S. Johnson
+ PDF Chat	On multiplicative graphs and the product conjecture	1988	Roland Häggkvist Pavol Hell Donald J. Miller Víctor Neumann Lara
+	On unavoidable digraphs in orientations of graphs	1987	Gary S. Bloom Stefan Burr
+	Representations of graphs by means of products and their complexity	1981	Jaroslav Nešetřil
+ PDF Chat	Some new good characterizations for directed graphs	1984	Pavel Komárek