Alguns problemas computacionais da Teoria dos Grafos:
- isomorfismo
- caminho mínimo
- circuito hamiltoniano
- circuito de comprimento máximo
- ciclo euleriano
- ciclo do carteiro chinês
- conjunto estável máximo
- emparelhamento máximo
- coloração de vértices
- coloração de arestas
- planaridade
- conexidade
- coleções disjuntas de caminhos (fluxo)
Na verdade, a Teoria dos Grafos não se limita a problemas computacionais. Há uma importante parte da teoria que trata das relações entre vários parâmetros de um grafo: a relação entre o tamanho de um conjunto estável máximo e o tamanho de uma clique máxima, a relação entre o número cromático e o grau máximo, a relação entre o número cromático e o gênus, etc.
Outra parte importante da teoria trata de grafos aleatórios e da evolução de seus parâmetros (como o número cromático, por exemplo) em função do número de vértices.