# Graphe scindé

En théorie des graphes, un graphe scindé ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977, et introduit indépendamment par Tyshkevich et Tchernyak en 1979$^,$$^,$.

## Exemples élémentaires

Un graphe scindé peut avoir plus d'une partition en une clique et un ensemble stable ; par exemple, le chemin a – b – c est un graphe scindé, dont les sommets peuvent être partitionnés de trois manières différentes :
* la clique $\{a,b\}$ et l'ensemble stable $\{c\}$ ;
* la clique $\{b,c\}$ et l'ensemble stable $\{a\}$ ;
* la clique $\{b\}$ et l'ensemble stable $\{a,c\}$.
Les graphes scindés peuvent être caractérisés par leurs sous-graphes induits interdits : un graphe est scindé si et seulement si aucun sous-graphe induit n'est un cycle sur quatre ou cinq sommets, ou n'est une paire d'arêtes disjointes (le complément d'un 4-cycle$^,$.

## Relation avec d'autres familles de graphes

De par leur définition, les graphes scindé sont clairement fermés par complémentation. Une autre caractérisation des graphes scindés fait intervenir la complémentation : ce sont des graphes cordaux dont les compléments sont également cordaux. Tout comme les graphes cordaux sont les graphes d'intersection de sous-arbres d'arbres, les graphes scindés sont les graphes d'intersection de sous-étoiles distinctes de graphes en étoile. Presque tous les graphes cordaux sont des graphes scindés, au sens où la fraction des graphes cordaux scindés parmi les graphes cordaux à n sommets qui sont scindé tend vers 1 lorsque n tend vers l'infini.
Comme les graphes cordaux sont parfaits, les graphes scindés le sont aussi. Les graphes à double scission, une famille de graphes dérivés de graphes scindés en doublant chaque sommet (la clique induit alors un anti-couplage et l'ensemble stable induit un couplage), figure, dans la preuve de Chudnovsky et al. 2006 du théorème des graphes parfaits fort, comme l'une des cinq classes de base de graphes parfaits à partir desquels tous les autres peuvent être formés.
Si un graphe est à la fois un graphe scindé et un graphe d'intervalle, alors son complément est à la fois un graphe scindé et un graphe de comparabilité, et vice versa. Les graphes de comparabilité scindés, et donc aussi les graphes d'intervalles scindés, peuvent être caractérisés en termes d'un ensemble de trois sous-graphes induits interdits. Les cographes scindés sont exactement les graphes à seuil. Les graphes de permutation scindés sont exactement les graphes d'intervalle dont les compléments sont des graphes d'intervalle ; ce sont les graphes de permutation pour des permutations symétriques gauches. Les graphes scindés ont un nombre cochromatique égal à 2.

## Problèmes algorithmiques

Soit G un graphe scindé, partitionné en une clique C et un ensemble stable I. Alors chaque clique maximale dans le graphe scindé est soit C lui-même, soit le voisinage d'un sommet dans I. Ainsi, il est facile d'identifier la clique maximale et, de manière complémentaire, l'ensemble stable maximal dans un graphe scindé. Dans tout graphe scindé, l'une des trois conditions suivantes est réalisée :
* Il existe un sommet $x$ dans $I$ tel que $C\cup \{x\}$ est complet. Dans ce cas, $C\cup \{x\}$ est une clique maximale et $I$ est un ensemble stable maximal.
* Il existe un sommet $x$ dans $C$ tel que $I\cup \{x\}$ est stable. Dans ce cas, $I\cup \{x\}$ est un ensemble stable maximum et $C$ est une clique maximum.
* $C$ est une clique maximale et $I$ est un ensemble stable maximal. Dans ce cas, G a une partition unique $(C,I)$ en une clique et un ensemble stable, $C$ est la clique maximale et $I$ est l'ensemble stable maximal.
Certains problèmes d'optimisation qui sont NP-complets sur des familles de graphes plus générales, y compris la coloration de graphes, deviennent simples sur des graphes scindés. Trouver une chaîne hamiltonienne reste NP-complet même pour les graphes scindés qui sont des graphes cordaux forts. Il est également connu que le problème de l'ensemble dominant minimum reste NP-complet pour les graphes scindés.

## Suites de degrés

Une propriété remarquable des graphes scindés est qu'ils peuvent être reconnus uniquement à partir de leurs suite de degrés. Soit $d_{1}\geq d_{2}\geq \cdots \geq d_{n}$d $_1$ ≥ d $_2$ ≥ ... ≥ d $_n$ la suite de degrés d'un graphe G et soit $m$ le plus grand indice $i$ tel que $d_{i}\geq i-1$. Alors G est un graphe scindé si et seulement si
    $\sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.$
Dans cas les m sommets avec les degrés les plus grands forment une clique maximale dans G, et les sommets restants constituent un ensemble stable$^,$$^,$$^,$$^,$. (Merris 2003) étudie plus à fond les suites de degrés de graphes scindés.

## Nombre de graphes scindés

Gordon F. Royle a démontré que les graphes scindé à n sommets sont en bijection avec certaines familles de Sperner. À l'aide de cette observation, il a établi une formule pour le nombre de graphes scindés non isomorphes à n sommets. Les premières valeurs de cette suite, à partir de n = 1, sont
    1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... suite A048194 de l'OEIS .
Ce résultat d'énumération a également été prouvé, en 1990, par Tyshkevich et Chernyak.