Direct growth of graphene by industrially scalable methods on suitable dielectric substrates is critical to the development of practical electronic and spintronic devices. Graphene growth by molecular beam epitaxy on the commensurate substrate h-BN(0001) and on other weakly interacting substrates has previously been demonstrated. We have been able to use MBE to grow graphene on incommensurate Co3O4(111), which we find involves formation of a deformed interfacial C layer due to some C atoms forming covalent bonds to oxide O sites, followed by epitaxial graphene growth in subsequent layers. These results suggest that similar graphene growth may be achievable on other p-type spinel-structured oxides, opening the door to new electronic or spintronic applications.