Finding domatic partitions in infinite graphs (Q888598)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6502782
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Finding domatic partitions in infinite graphs |
scientific article; zbMATH DE number 6502782 |
Statements
Finding domatic partitions in infinite graphs (English)
0 references
2 November 2015
0 references
Summary: We investigate the apparent difficulty of finding domatic partitions in graphs using tools from computability theory. We consider nicely presented (i.e., computable) infinite graphs and show that even if the domatic number is known, there might not be any algorithm for producing a domatic partition of optimal size. However, we prove that smaller domatic partitions can be constructed if we restrict to regular graphs. Additionally, we establish similar results for total domatic partitions.
0 references
domatic partitions
0 references
graph algorithms
0 references
infinite regular graphs
0 references
computability theory
0 references
0 references
0.8487581014633179
0 references
0.7804442644119263
0 references
0.7542526125907898
0 references
0.7521162033081055
0 references
0.7515373229980469
0 references
