scientific article; zbMATH DE number 1303205

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Theory of numerations, effectively presented structures (03D45) Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Review text

In this article we survey results of the last twenty years concerning recursive and on-line coloring of graphs. The subject began in the seventies as part of the effort by logicians to understand the effective content of various existence theorems in mathematics. One of the areas chosen for investigation was graph theory, and in particular, graph coloring. It is well known, and easy to prove using any of a number of forms of the compactness theorem, that for any finite number \(k\), an infinite graph \(G\) is \(k\)-colorable iff every finite subgraph of \(G\) is \(k\)-colorable. It also is not hard to show that this is not an effective result. There exists a recursive \(k\)-colorable graph \(G\) which cannot be \(k\)-colored by any recursive function. Given such a state of affairs one can either study the degrees of unsolvability of \(k\)-colorings of \(G\) or try to find recursive colorings of \(G\) which do not use too many extra colors. Here we take the second course. Our goal is to discover interesting classes of recursive \(k\)-colorable graphs which can be recursively colored with a bounded number of colors. For the entire collection see [Zbl 0905.03002].

Recommendations

Cited in

(22)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249728)