The complexity of infinite H-colouring

DOI10.1006/JCTB.1994.1040zbMATH Open0802.05038OpenAlexW2039793369MaRDI QIDQ1333335FDOQ1333335

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

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

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)

Cited In (10)

• The complexity of restricted graph homomorphisms
• Fast left Kan extensions using the chase
• Graph homomorphisms with infinite targets
• Endomorphisms of Cayley digraphs of rectangular groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the distance and multidistance graph embeddability problem
• Non-dichotomies in Constraint Satisfaction Complexity
• Constraint Satisfaction Problems with Infinite Templates
• An initial study of time complexity in infinite-domain constraint satisfaction

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)