Colorings of the d-regular infinite tree

The existence of small d-regular graphs of a prescribed girth g is equivalent to the existence of certain codes in the d-regular infinite tree. We show that in the tree “perfect” codes exist, but those are usually not “graphic”. We also give an explicit coloring that is “nearly perfect” as well as “nearly graphic”.