On the finiteness of the recursive chromatic number (Q1295384)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the finiteness of the recursive chromatic number |
scientific article |
Statements
On the finiteness of the recursive chromatic number (English)
0 references
29 May 2000
0 references
An \(A\)-recursive graph is an infinite graph whose vertex and edge sets are recursive and such that the neighbors of any node can be determined recursively. It is shown that if \(A\) is r.e. and not recursive and if \(k\) is any integer, then there exists an \(A\)-recursive graph that is 2-colorable but that cannot be recursively colored with \(k\) colors. This result was previously known to hold for recursive graphs, that is, for graphs whose vertex and edge sets are recursive but with no effectiveness property for determining the neighbors of a node.
0 references
recursive graph
0 references
highly recursive graph
0 references
recursive coloring
0 references
0 references