La couverture et le partitionnement de graphe sont deux problèmes centraux en théorie des graphes qui ont de nombreuses applications dans des domaines variés comme la fouille de données (data mining) ou les réseaux (clustering, communautés, ...). Le premier problème consiste à couvrir le graphe par un ensemble de sommets ou d'arêtes ou encore de chemins, cycles ou sous-graphes, de la meilleure façon possible. Le second problème consiste à découper de façon optimale le graphe en « morceaux » suivant plusieurs contraintes. La coloration de graphe est un exemple de problème de partitionnement de graphes qui fait l'objet d'une recherche internationale très active et fleurissante. L'objectif de cette thèse est d'étudier de façon conjointe et généralisée ces deux paramètres. Cela amènera à prendre en compte des contraintes portant sur la séparation des couleurs, comme
dans les cas des L(p,q)-colorations et des [r,s,t]-colorations, ainsi que sur un voisinage étendu. En particulier, on s'intéressera au problème du packing coloring introduit récemment qui est à la fois un problème de coloration et de couverture de graphe. Des premiers résultats sur ce paramètre ont déjà été trouvé par des membres de l'équipe.
Les application des problèmes étudiés dans cette thèse iront des aspects réseaux aux fouille de données.