𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the finiteness of the recursive chromatic number

✍ Scribed by William I. Gasarch; Andrew C.Y. Lee

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
559 KB
Volume
93
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

✦ Synopsis

A recursive graph is a graph whose vertex and edge sets are recursive.

A highly recursive graph is a recursive graph that also has the following property: one can recursively determine the neighbors of a vertex. Both of these have been studied in the literature. We consider an intermediary notion: Let A be a set. An A-recursive graph is a recursive graph that also has the following property: one can recursively-in-A determine the neighbors of a vertex. We show that, if A is r.e. and not recursive, then there exists A-recursive graphs that are 2-colorable but not recursively k-colorable for any k. This is false for highly-recursive graphs but true for recursive graphs. Hence A-recursive graphs are closer in spirit to recursive graphs than to highly recursive graphs.

πŸ“œ SIMILAR VOLUMES

On the mean chromatic number
On the mean chromatic number
✍ Martin Anthony πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 209 KB

The mean chromatic number of a graph is a measure of the expected performance of the greedy vertex-colouring algorithm when each ordering of the vertices is equally likely. Some results on the value of the mean chromatic number and its asymptotic behaviour are presented.

On the chromatic number of disk graphs
On the chromatic number of disk graphs
✍ Malesi?ska, Ewa; Piskorz, Steffen; WeiοΏ½enfels, Gerhard πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 172 KB πŸ‘ 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their

On the cost-chromatic number of graphs
On the cost-chromatic number of graphs
✍ John Mitchem; Patrick Morriss πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 566 KB

We consider vertex colorings in which each color has an associated cost, incurred each time the color is assigned to a vertex. For a given set of costs, a minimum-cost coloring is a vertex coloring which makes the total cost of coloring the graph as small as possible. The cost-chromatic number of a

On the oriented chromatic number of grid
On the oriented chromatic number of grids
✍ Guillaume Fertin; AndrΓ© Raspaud; Arup Roychowdhury πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 111 KB

In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph G without symmetric arcs such that (i) no two neighbors in G are assigned the same color, and (ii) if two vertices u and v such that (u, v) ∈ A(G) are assigned colors c(u)