Дополнение графа: различия между версиями

*[[Задача о независимом множестве|Независимое множество]] графа является [[Клика (теория графов)|кликой]] в дополнении графа и наоборот.

*Дополнение любого [[Граф без треугольников|графа без треугольников]] не содержит [[Граф без клешней|клешней]].

*{{не переведено 5|Кограф|Кографы||Cograph}} определяются как графы, которые можно построить из единственной точки [[Операции над графами|несвязанным объединеним]] и операцией дополнения. Кографы образуют семейство самодополнительных графов — дополнение любого кографа является другим (возможно, отличным от исходного) кографом.