Non-Recursively Constructible Recursive Families of Graphs

Colleen Bouey, Christina Graves, Aaron Ostrander, Gregory Palma


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.


Tutte polynomial

Full Text: PDF