Non-Recursively Constructible Recursive Families of Graphs

Abstract

In a publication by Noy and Ribó, it was shown that recursively constructible families of graphs are recursive.  The authors also conjecture that the converse holds; that is, recursive families are also recursively constructible.  In this paper, we provide two specific counterexamples to this conjecture, which we then extend to an infinite family of counterexamples.