This question is probably going to turn into a community-wiki style list of favourite open problems concerning permutation groups and graphs. So, for what it's worth, here are two of mine:
The Weiss Conjecture: Let $G$ act vertex-transitively on some graph $\mathcal{G}$ of valency $k$. Let $v$ be a vertex of $\mathcal{G}$ and assume that $G_v$ acts primitively on its neighbours. Then $|G_v| \leq f(k)$ where $f:\mathbb{N}\to \mathbb{N}$ is some function depending only on $k$.
There is a wealth of work on this conjecture by many people. I would particular recommend this paper by Potocnik, Spiga and Verret, where the conjecture is discussed at length and some more general conjectures are also proposed. I'd also recommend this paper by Praeger, Pyber, Spiga and Szabo, in which substantial progress towards a proof of the conjecture is made.
All of the papers dealing with this conjecture make heavy use of permutation group techniques; recent papers also tend to make use of results coming out of the classification of finite simple groups.
The classification of regular maps: A map is a `nice' embeding of a graph on a surface, in a way that generalizes the notion of a planar graph. The map is regular if (to choose one of several slightly different definitions) it admits an automorphism group that acts as homeomorphisms on the surface, and is transitive on vertex-edge incident pairs.
The subject is very old (cf. the platonic solids), but the modern concern with these things began with Brahana and Coxeter and, then a few years later, with this beautiful paper by Jones and Singerman. There is now a wealth of literature aimed at classifying regular maps subject to constraints on, for instance, the underlying surface, the underlying graph, or the automorphism group. Prominent authors include Conder, Siran, Jones, Nedela, Breda d'Azevedo, Tucker, Archdeacon etc etc. Permutation group techniques are commonly used, as well as ideas from topology, group generation, Riemann surfaces etc.
The notion of a map is closely related to the important notion of a dessin d'enfant which was the subject of a famous paper by Grothendieck. There is a whole other school of work looking at maps from this perspective, however (to my knowledge) the emphasis in this school is not on the permutation group approach, and so may not be of so much interest to you.