Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.

DOI10.1016/S0304-3975(02)00329-8zbMath1044.68163OpenAlexW1972363616MaRDI QIDQ1401202

Antonio Puricella, Iain A. Stewart

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00329-8

zbMATH Keywords

\(H\)-colourable subgraphs

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Dichotomies for classes of homomorphism problems involving unary functions

Cites Work

• On the complexity of H-coloring
• On generating all maximal independent sets
• List homomorphisms to reflexive graphs
• \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
• List homomorphisms and circular arc graphs
• Complete Problems Involving Boolean Labelled Structures and Projection Transactions
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item