L' ISGCI répertorie plus de 1100 classes de graphiques. Pour beaucoup d'entre eux, nous savons si le JEU INDÉPENDANT peut être décidé en temps polynomial; elles sont parfois appelées classes IS-easy . Je voudrais compiler une liste de classes IS-easy maximales . Ces classes forment ensemble la...
Une griffe est un K1,3K1,3K_{1,3} . Un algorithme trivial détectera une griffe en temps O(n4)O(n4)O(n^4) . Cela peut être fait dans O(nω+1)O(nω+1)O(n^{\omega+1}) , où ωω\omega est l'exposant de la multiplication matricielle rapide, comme suit: prendre le sous-graphe induit par N[v]N[v]N[v] pour...
Les graphiques sans X sont ceux qui ne contiennent aucun graphique de X comme sous-graphique induit. Un trou est un cycle avec au moins 4 sommets. Un trou impair est un trou avec un nombre impair de sommets. Un antihole est le complément d'un trou. Les graphiques libres (trous impairs, anti-trous...
Le problème du cycle hamiltonien (HC) consiste à trouver un cycle passant par tous les sommets d'un graphe non orienté donné. Le problème des vendeurs ambulants (TSP) consiste à trouver un cycle qui passe par tous les sommets d'un graphique pondéré sur les bords et minimise la distance totale...
Soit et notons G k l'ensemble de tous les graphes qui peuvent être incrustés sur une surface du genre k de telle sorte que tous les sommets soient situés sur la face externe . Par exemple, G 0 est l'ensemble des graphes planaires externes. La largeur d'arbre des graphes dans G k peut-elle être...
Il est formulé en étendant les graphiques de seuil . Étant donné un graphique de seuil où C est la clique et I est l'ensemble indépendant, mon extension est la suivante: Chaque sommet v ∈ I peut être remplacé par une nouvelle clique K v de telle sorte que les sommets de K v aient le mêmes voisins...
J'essaie de trouver un graphique avec ces propriétés pour mes études, mais malheureusement je ne trouve pas un tel graphique. Est-ce que quelqu'un sait s'il y a ce graphique, ou pourquoi est-il impossible
Soit un graphe qui est l'union disjointe d'une clique et d'un ensemble indépendant, ie ggGG = Kn1+ Kn2¯¯¯¯¯¯¯¯= Kn1+ Jen2.g=Kn1+Kn2¯=Kn1+jen2.G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . La classe de graphes de tous ces graphes est caractérisée par les sous-graphes induits interdits...