Cographe

Un cographe est un graphe simple qui peut-être construit de manière récursive selon les règles suivantes :

• le graphe à un sommet est un cographe,
• le complémentaire d'un cographe est un cographe,
• l'union de deux cographes est un cographe.

Le "join" de deux graphes disjoints ${\displaystyle G_{1}=(V_{1},E_{1})}$ et ${\displaystyle G_{2}=(V_{2},E_{2})}$, est l'opération qui consiste à créer un nouveau graphe ${\displaystyle G=(V,E)}$, où ${\displaystyle V=V_{1}\cup V_{2}}$ et ${\displaystyle E=E_{1}\cup E_{2}\cup \{(i,j)|i\in V_{1},j\in V_{2}\}}$. Cette opération est en fait le complémentaire de l'union des complémentaires.

Un cographe est alors un graphe qui peut être formé à partir des graphes à un sommet, par "join" et par union.

Il existe de nombreuses caractérisations des cographes, notamment :

• les cographes sont les graphes ${\displaystyle P_{4}}$-free, c'est-à-dire ceux qui n'ont pas le chemin sur quatre sommets comme sous-graphe induit[2];
• les cographes sont graphes pour lesquels tous les sous-graphes induits non triviaux possèdent deux sommets ayant le même voisinage.
• les cographes sont les graphes d'inversions des permutations séparables.

• La famille des cographes sur Information System on Graph Classes and their Inclusions
• (en) Eric W. Weisstein, « Cograph », sur MathWorld