On the complexity of H-coloring

1990/02/01 by Pavol Hell, Jaroslav Nešetřil · 10 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complete coloring #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph homomorphism #Graph power #Greedy coloring #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics

paper · doi:10.1016/0095-8956(90)90132-j

crossref issued 1990/02/01 · crossref published 1990/02/01 · crossref published-print 1990/02/01 · openalex publication_date 1990/02/01 · crossref created 2004/12/22 · crossref deposited 2021/07/02 · openalex created_date 2025/10/10 · crossref indexed 2026/04/08 · openalex updated_date 2026/07/23

Cited by

• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• On Languages Describing Large Graph Classes
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Graph homomorphisms: structure and symmetry
• On the Homomorphism Order of Labeled Posets
• Partial covers of graphs
• Colouring, constraint satisfaction, and complexity
• Dichotomies and Duality in First-order Model Checking Problems
• Graph homomorphism [wikipedia]