Le nombre approximatif de colorations semble être facile sur les graphiques mineurs exclus utilisant l' algorithme de Jung / Shah. Quels sont les autres exemples de problèmes difficiles sur les graphiques généraux mais faciles sur les graphiques mineurs? Mise à jour 10/24 Il semble suivre les...
Ci-dessous, MSO désigne la logique monadique du second ordre des graphiques avec des quantifications de sommets et de contours. Soit une petite famille fermée de graphes. Il découle de la théorie de graphe mineur de Robertson et Seymour que F est caractérisée par une liste finie H 1 , H 2 , . . . ,...
Je voudrais savoir s'il existe des bibliothèques de graphiques gratuites pour tester si un ensemble spécifique de mineurs existe dans un graphique
La largeur d'arbre joue un rôle important dans les algorithmes FPT, en partie parce que de nombreux problèmes sont paramétrés FPT par la largeur d'arbre. Une notion connexe, plus restreinte, est celle de largeur de chemin. Si un graphe a une largeur de chemin , il a également une largeur d'arbre au...
Il est bien connu que K5K5K_5 et K3,3K3,3K_{3,3} sont des mineurs interdits pour les graphes planaires. Il existe des centaines de mineurs interdits pour les graphiques intégrables sur un tore. Le nombre de mineurs interdits pour les graphes intégrables à la surface du genre g est une fonction...
Cette question est similaire à l' une de mes précédentes. Il est connu que est un mineur interdit pour les graphiques de largeur d'arbre au plus .Kt+2Kt+2K_{t+2}ttt Existe-t-il une famille infinie de graphiques bien paramétrés et bien construits (autres que les graphiques complets et les graphiques...
Les graphes planaires sont . Ces graphiques peuvent être décomposés en composants tri-connectés, qui sont connus pour être des composants plans ou .K3 , 3K3,3K_{3,3}K5K5K_5 Existe-t-il une décomposition aussi "sympa" des graphes du genre un? Dans leur travail séminal sur les mineurs de graphes,...
Considérez le problème suivant. Entrée: Un graphique non orienté . Sortie: Un graphique H qui est un mineur de G avec la densité de bord la plus élevée parmi tous les mineurs de G , c'est-à-dire avec le rapport le plus élevé | E ( H ) | / | V ( H ) |
Si est un graphique avec un degré maximum 3 et est un mineur de H , alors G est un mineur topologique de H .GGGHHHGGGHHH Wikipedia cite ce résultat de la "théorie des graphes" de Diestel. Il est répertorié comme Prop 1.7.4 dans la dernière version du livre. Le livre manque de preuve ou de citation....
Soit kkk fixé et GGG soit un graphe (connecté). Si je ne me trompe pas, il résulte des travaux de Bodlaender [1, Theorem 3.11] que si la largeur d'arbre de GGG est à peu près au moins 2k32k32k^3 , alors GGG contient une étoile K1,kK1,kK_{1,k} tant que mineur. Pouvons-nous rendre le terme 2k32k32k^3...
Soit C4C4C_4 un cycle à quatre sommets. Pour un graphe arbitraire GGG avec nnn sommets et m arêtes disons m>nn−−√m>nnm>n\sqrt n , combien deC4C4C_4existent? Y a-t-il une limite inférieure pour
Le théorème de Courcelle stipule que chaque propriété de graphe définissable en logique monadique du second ordre peut être décidée en temps linéaire sur des graphes de largeur d'arbre bornée . C'est l'un des méta-théorèmes algorithmiques les plus connus. Motivé par le théorème de Courcelle, j'ai...
Cette question est double et est principalement orientée vers la référence: Y a-t-il un endroit où les principales intuitions pour prouver le théorème mineur du graphe sont données, sans trop entrer dans les détails? Je sais que la preuve est longue et difficile, mais il doit sûrement y avoir des...
On me donne un graphique avec une largeur d' arbre k et un degré arbitraire, et je voudrais trouver un sous-graphique H de G (pas nécessairement un sous-graphique induit) tel que H ait un degré constant et sa largeur d'arbre soit aussi élevée que possible. Formellement, mon problème est le suivant:...
Le théorème de Robertson – Seymour dit que toute famille gg\mathcal G de graphes mineurs peut être caractérisée par un nombre fini de mineurs interdits. Existe-t-il un algorithme qui, pour une entrée gg\mathcal G délivre les mineurs interdits ou est-ce indécidable? Évidemment, la réponse pourrait...