The complexity of infinite H-colouring

DOI10.1006/JCTB.1994.1040MaRDI QIDQ1333335zbMATH OpenOpenAlexFDO

Authors Bruce L. Bauslaugh

Publication date 28 November 1994

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1994.1040

zbMATH Keywords

complexityhomomorphismrecursively enumerable degreesrecursive graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• On the complexity of H-coloring
• scientific article; zbMATH DE number 4008418
• scientific article; zbMATH DE number 434895
• Complexity of correspondence \(H\)-colourings
• scientific article; zbMATH DE number 1953088
• The colouring number of infinite graphs
• Essentially infinite colourings of hypergraphs
• The complexity of \(H\)-colouring of bounded degree graphs
• Essentially Infinite Colourings of Graphs
• On the complexity of \(H\)-colouring planar graphs

Cited in

(10)

• The complexity of restricted graph homomorphisms
• Graph homomorphisms with infinite targets
• scientific article; zbMATH DE number 434895 (Why is no real title available?)
• Constraint Satisfaction Problems with Infinite Templates
• Non-dichotomies in Constraint Satisfaction Complexity
• Endomorphisms of Cayley digraphs of rectangular groups
• An initial study of time complexity in infinite-domain constraint satisfaction
• Fast left Kan extensions using the chase
• scientific article; zbMATH DE number 4162940 (Why is no real title available?)
• On the distance and multidistance graph embeddability problem

This page was built for publication: The complexity of infinite \(H\)-colouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1333335)