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.
@article{10_37236_5089,
author = {Matthew Jura and Oscar Levin and Tyler Markkanen},
title = {Finding domatic partitions in infinite graphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {3},
doi = {10.37236/5089},
zbl = {1323.05102},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5089/}
}
TY - JOUR
AU - Matthew Jura
AU - Oscar Levin
AU - Tyler Markkanen
TI - Finding domatic partitions in infinite graphs
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/5089/
DO - 10.37236/5089
ID - 10_37236_5089
ER -
%0 Journal Article
%A Matthew Jura
%A Oscar Levin
%A Tyler Markkanen
%T Finding domatic partitions in infinite graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5089/
%R 10.37236/5089
%F 10_37236_5089
Matthew Jura; Oscar Levin; Tyler Markkanen. Finding domatic partitions in infinite graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 3. doi: 10.37236/5089
