This is in no way a definitive answer, and I do not intend it as such.
Many problems of interest to computer scientists can be phrased as graph problems, and as a result graph theory shows up quite a lot in complexity theory. The computational effort required to determine where two graphs are isomorphic, for example, is currently a topic of much interest in complexity theory (it is neither known to be NP-complete nor contained in P, BPP or BQP, but is clearly in NP). Graph non-isomorphism, on the other hand, has a very nice zero-knowledge proof (another area of study in complexity theory). Many complexity classes have graph problems which are complete for that class (under some reduction).
However it is not just complexity theory that makes use of graph theory. As you can see from some of the other answers, there is quite an array of problems for which the language of graph theory is most appropriate. There are far to many applications to provide a diffinitive list, so instead I will leave you with an example of how graph theory plays a fundamental role in my own area of research.
Measurement-based quantum computation is a model of computation which does not have a counterpart in the classical world. In this model, the computation is driven by making measurements on a special class of quantum states. These states are known as graph states, because each state can be uniquely identified with an undirected graph with a number of vertices equal to the number of qubits in the graph state. This link with graph theory is more than coincidental, however. We know that an important class of measurements (Pauli-basis measurements in case you are interested) map the underlying graph state to a new graph state on one less qubit, and the rules by which this occurs are well understood. Further, properties of the underlying graph family (it's flow and g-flow) determined fully whether it supports universal computation. Lastly, for any graph G' which can be reached from another graph G by an arbitrary sequence of complementing the edges of the neighbourhood of a vertex can be reached by single-qubit operations alone, and so are equally powerful as a resource for computation. This is interesting because the number of edges, maximum of the vertex degrees, etc. can change drastically.