Structure de graphiques qui excluent une correspondance parfaite sur quatre sommets en tant que graphique induit

Je suis intéressé à comprendre la structure de la classe des graphes telle sorte qu'il n'y ait pas de sous-graphe induit par un sommet sur quatre sommets qui soit une correspondance parfaite. Autrement dit pour quatre sommets dans si et sont des arêtes, le graphique doit avoir au moins une arête de plus sur les quatre sommets. Cette classe a-t-elle été étudiée précédemment? Toutes les références ou idées seraient appréciées. Nous comprenons cette classe lorsqu'elle est restreinte aux graphes bipartis mais le cas général semble plus délicat. $G$ $a,b,c,d$ $G$ $ab$ $cd$

graph-theory Chandra Chekuri
la source

Vous voulez ajouter ici une propriété importante des graphes libres de

, à savoir que le nombre d'ensembles indépendants maximaux dans ces graphes est polynomial dans le nombre de sommets. En fait, pour tout graphique fixe sans

existe un nombre polynomial d'ensembles indépendants maximaux. Voir la référence suivante pour plus d'informations. "Résultats de complexité sur des graphiques avec peu de cliques." Mathématiques discrètes et informatique théorique 9.1 (2007): 127-135.

2 K_{2}

$2K_2$

t

$t$

t K_{2}

$tK_2$

Chandra Chekuri

Structure de graphiques qui excluent une correspondance parfaite sur quatre sommets en tant que graphique induit

Réponses: