Graphique fractionné

En théorie des graphes , une branche des mathématiques, un graphe divisé est un graphe dans lequel les sommets peuvent être partitionnés en une clique et un ensemble indépendant . Les graphes divisés ont été étudiés pour la première fois par Földes et Hammer (1977a, 1977b), et introduits indépendamment par Tyshkevich et Chernyak (1979), où ils ont appelé ces graphes « graphes polaires » ( en russe : полярные графы ).

Un graphe divisé peut avoir plus d'une partition en une clique et un ensemble indépendant ; par exemple, le chemin a – b – c est un graphe divisé, dont les sommets peuvent être partitionnés de trois manières différentes :

1. la clique { a , b } et l'ensemble indépendant { c }
2. la clique { b , c } et l'ensemble indépendant { a }
3. la clique { b } et l'ensemble indépendant { a , c }

Les graphes fractionnés peuvent être caractérisés en termes de leurs sous-graphes induits interdits : un graphe est fractionné si et seulement si aucun sous-graphe induit n'est un cycle sur quatre ou cinq sommets, ou une paire d'arêtes disjointes (le complément d'un 4-cycle).

D'après la définition, les graphes séparés sont clairement fermés sous complémentation . Une autre caractérisation des graphes séparés implique la complémentation : ce sont des graphes de cordes dont les compléments sont également de cordes. Tout comme les graphes de cordes sont les graphes d'intersection de sous-arbres d'arbres, les graphes séparés sont les graphes d'intersection de sous-étoiles distinctes de graphes d'étoiles . Presque tous les graphes de cordes sont des graphes séparés ; c'est-à-dire que dans la limite où n tend vers l'infini, la fraction de graphes de cordes à n sommets qui sont séparés tend vers un.

Les graphes chordaux étant parfaits , les graphes séparés le sont aussi. Les graphes séparés doubles , une famille de graphes dérivés des graphes séparés en doublant chaque sommet (de sorte que la clique induit une anticorrespondance et l'ensemble indépendant induit une correspondance), figurent en bonne place comme l'une des cinq classes de base de graphes parfaits à partir desquelles tous les autres peuvent être formés dans la preuve par Chudnovsky et al. (2006) du théorème du graphe parfait fort .

Si un graphe est à la fois un graphe fractionné et un graphe d'intervalles , alors son complémentaire est à la fois un graphe fractionné et un graphe de comparabilité , et vice versa. Les graphes de comparabilité fractionnés, et donc aussi les graphes d'intervalles fractionnés, peuvent être caractérisés en termes d'un ensemble de trois sous-graphes induits interdits. cographes fractionnés sont exactement les graphes de seuil . Les graphes de permutation fractionnés sont exactement les graphes d'intervalles qui ont des compléments de graphes d'intervalles ; ce sont les graphes de permutation des permutations fusionnées de manière asymétrique . Les graphes fractionnés ont un nombre cochromatique de 2.

Soit G un graphe divisé, partitionné en une clique C et un ensemble indépendant i . Alors toute clique maximale dans un graphe divisé est soit C lui-même, soit le voisinage d'un sommet dans i . Ainsi, il est facile d'identifier la clique maximale, et complémentairement l' ensemble indépendant maximal dans un graphe divisé. Dans tout graphe divisé, l'une des trois possibilités suivantes doit être vraie :

1. Il existe un sommet x dans i tel que C ∪ { x } soit complet. Dans ce cas, C ∪ { x } est une clique maximale et i est un ensemble indépendant maximal.
2. Il existe un sommet x dans C tel que i ∪ { x } soit indépendant. Dans ce cas, i ∪ { x } est un ensemble indépendant maximal et C est une clique maximale.
3. C est une clique maximale et i est un ensemble indépendant maximal. Dans ce cas, G possède une partition unique ( C , i ) en une clique et un ensemble indépendant, C est la clique maximale et i est l'ensemble indépendant maximal.

D'autres problèmes d'optimisation qui sont NP-complets sur des familles de graphes plus générales, y compris la coloration de graphes , sont tout aussi simples sur des graphes fractionnés. La recherche d'un cycle hamiltonien reste NP-complet même pour les graphes fractionnés qui sont des graphes fortement cordaux . Il est également bien connu que le problème de l'ensemble dominant minimum reste NP-complet pour les graphes fractionnés.

Une propriété remarquable des graphes fractionnés est qu'ils peuvent être reconnus uniquement à partir de leurs suites de degrés . Soit la suite de degrés d'un graphe G d 1 _≥ d 2 _≥ … ≥ d _n , et soit m la plus grande valeur de i telle que d _i ≥ i – 1 . Alors G est un graphe fractionné si et seulement si

Si tel est le cas, alors les m sommets avec les plus grands degrés forment une clique maximale dans G , et les sommets restants constituent un ensemble indépendant.

La splittance d'un graphe arbitraire mesure dans quelle mesure cette inégalité n'est pas vraie. Si un graphe n'est pas un graphe divisé, alors la plus petite séquence d'insertions et de suppressions d'arêtes qui le transforme en graphe divisé peut être obtenue en additionnant toutes les arêtes manquantes entre les m sommets ayant les degrés les plus élevés et en supprimant toutes les arêtes entre les paires des sommets restants ; la splittance compte le nombre d'opérations dans cette séquence.

Royle (2000) a montré que les graphes séparés à n sommets ( non étiquetés ) sont en correspondance bijective avec certaines familles de Sperner . En utilisant ce fait, il a déterminé une formule pour le nombre de graphes séparés non isomorphes sur n sommets. Pour les petites valeurs de n , à partir de n = 1, ces nombres sont

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (séquence A048194 dans l' OEIS ).

Ce résultat énumératif a également été prouvé précédemment par Tyshkevich et Chernyak (1990).

• Un chapitre sur les graphes divisés apparaît dans le livre de Martin Charles Golumbic , « Algorithmic Graph Theory and Perfect Graphs ».