Les problèmes combinatoires basés sur le partitionnement de graphe permettent de modéliser un grand nombre d'applications pratiques dans des domaines aussi variés que la planification de missions ou la construction de tournées de véhicules en logistique. Ces applications peuvent toutes être considérées comme un problème de partitionnement de graphe par des patrons tels que des cycles, des chemins ou des arbres.
Le développement des technologies de l’Internet pour la construction et le partage des connaissances et la demande croissante de visibilité font évoluer les pratiques des chercheurs et les conduisent notamment à investir les nouveaux outils offerts par le web (archives ouvertes, wikis, blogs, réseaux sociaux…).