Struktur von Graphen, die eine perfekte Übereinstimmung auf vier Eckpunkten als induzierten Graphen ausschließen

Ich bin daran interessiert, die Struktur der Klasse von Graphen so zu verstehen, dass es auf vier Eckpunkten keinen vertexinduzierten Subgraphen gibt, der perfekt passt. Anders ausgedrückt für alle vier Eckpunkte a , b , c , d in Wenn und Kanten sind, sollte der Graph mindestens eine Kante mehr auf den vier Eckpunkten haben. Wurde diese Klasse schon einmal studiert? Alle Verweise oder Einblicke wäre dankbar. Wir verstehen diese Klasse, wenn sie auf zweigeteilte Graphen beschränkt ist, aber der allgemeine Fall scheint schwieriger zu sein.$G$$a,b,c,d$$G$$ab$$cd$

Ja; Sie werden als -freie Graphen bezeichnet$2K_2$ . Einige zusätzliche Referenzen:

• „ Auf Härte und Hamilton von -Freier Graphs$2K_2$ “
• " Die maximale Anzahl von Kanten in -freien Graphen mit begrenztem Grad$2K_2$ ";
• " Zwei Charakterisierungen minimaler Triangulationen von -freien Graphen$2_{K2}$ "