Najprostszym przykładem podziału grafu jest podział grafu pełnego na dwie izomorficzne
części. Jeśli taki podział istnieje, to każdą z nich nazywamy grafem samodopełniającym gdyź jest izomorficzna ze swoim dopełnieniem.
Jest oczywiste, źe jeżeli 
jest podgrafem
grafu samodopelniającego (w 
), to graf
pełny zawiera dwie krawędziowo-rozłączne kopie grafu . Na ogół twierdzenie odwrotne nie
jest prawdziwe, ale przy pewnych dodatkowych założeniach ... .
Zarówno pojęcie grafu samodopełniającego, jak i grafów 2-pakowalnych zostało uogólnione na różne sposoby. Referat zawiera omówienie kilku z nich.