A complete classification is given of finite primitive permutation groups which contain a regular subgroup of square-free order. Then a collection
PNC{\cal P}{\cal N}{\cal C}
of square-free numbers
n is obtained such that there exists a vertex-primitive non-Cayley graph on
n
vertices if and only if
n is a member of
PNC{\cal P}{\cal N}{\cal C}
.