Le problème du plus grand graphe partiel commun a été introduit en premier par Bokhari pour résoudre le problème d'affectation de tâches à des processeurs tout en maximisant les demandes de communications entre tâches. Ce problème donne également une mesure de similarité entre deux graphes et est utilisé comme outil pour comparer des molécules. Nous proposons de nouvelles formulations linéaires pour le résoudre et les comparons numériquement aux formulations de la littérature.