Below are some concrete problems, perhaps leading to a concrete student project!
First some words are in order about undertaking such a project.
The problems below reflect my own areas of research, but naturally the background and interests of the student are equally as important.
Variations on the topics suggested below are welcome. In all cases discussion is required in order to formulate a realistic project proposal. The outcome of a project may range from understanding the nuts and bolts of an existing research level project to generating original research of one's own. Although some projects lend themselves to a computational approach and their substance may lie in developing and programming algorithms, my own competence in programming is limited, to put it charitably, so I would be unlikely to be able to give advice on this aspect. (On the other hand, then, I welcome those skilled in programming in attacking some thorny problems that are beyond pencil and paper...!) Even so, any project that is to be successfuly undertaken will require understanding of theoretical results.
Independent of the scale and final outcome of a project upon which we reach a mutual agreement, it is expected that at the end of the project you will have learned about methods and concepts that are of theoretical as well as practical importance. In general, they will relate to algebraic graph theory, enumerative combinatorics, graphs on surfaces or graph homomorphisms.
Here are some example project sketches:
Integer flows of graphs
Non-Abelian flows for embedded graphs
Homomorphisms between graphs with added structure (such as an embedding) and their enumeration
[details to follow... page under construction]