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

complexityhomomorphismrecursive graphsrecursively enumerable degrees

Mathematics Subject Classification ID

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

Review text

For a fixed graph \(H\), the homomorphism problem for \(H\) is the problem of determining whether or not there is a homomorphism of a finite input graph \(G\) into \(H\). We investigate the complexity of this problem when \(H\) is allowed to be countably infinite and show that there exist recursive graphs with unsolvable homomorphism problems, as well as recursive graphs with solvable homomorphism problems of very high complexity. In fact, we show that there exist graphs with arbitrary recursively enumerable degrees of unsolvability.

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

(11)

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

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)