The complexity of infinite \(H\)-colouring
type: Item
instance of: scholarly article
title: The complexity of infinite \(H\)-colouring
zbMATH Open document ID: 0802.05038
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-11-28T00:00:00Z
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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 03D40
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 638656
zbMATH Keywords: homomorphism
zbMATH Keywords: recursive graphs
zbMATH Keywords: complexity
zbMATH Keywords: recursively enumerable degrees
author: Bruce L. Bauslaugh
MaRDI profile type: Publication
full work available at URL: jctb.1994.1040
OpenAlex ID: W2039793369
DOI: 10.1006/JCTB.1994.1040
Recommended article: On the complexity of H-coloring
Recommended article: Q3758852
Recommended article: Q3139749
Recommended article: Complexity of correspondence \(H\)-colourings
Recommended article: Q4414491
Recommended article: The colouring number of infinite graphs
Recommended article: Essentially infinite colourings of hypergraphs
Recommended article: The complexity of \(H\)-colouring of bounded degree graphs
Recommended article: Essentially Infinite Colourings of Graphs
Recommended article: On the complexity of \(H\)-colouring planar graphs
description: scientific article; zbMATH DE number 638656