Finding Domatic Partitions in Infinite Graphs

  • Matthew Jura
  • Oscar Levin
  • Tyler Markkanen
Keywords: Domatic partitions, Graph algorithms, Infinite regular graphs, Computability theory

Abstract

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.
Published
2015-09-20
Article Number
P3.39