Alguns problemas computacionais da teoria dos grafos:

Mas a teoria dos grafos não se limita a problemas computacionais.  Uma importante parte da teoria que trata das relações entre vários parâmetros de um grafo:  a relação entre o número cromático e o gênus do grafo, por exemplo.

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.