Non-Recursively Constructible Recursive Families of Graphs

TitleNon-Recursively Constructible Recursive Families of Graphs
Publication TypeJournal Article
Year of Publication2012
AuthorsBouey, C, Graves, C, Ostrander, A, Palma, G
JournalThe Electronic Journal of Combinatorics
Date Published2012/04/16

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.