Citation montrant que les mineurs sont des mineurs topologiques pour les graphiques sous-cubiques

12

Si est un graphique avec un degré maximum 3 et est un mineur de H , alors G est un mineur topologique de H .GHGH

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.

Les allées et venues sont-elles connues pour une preuve (originale) de cela?

De plus, existe-t-il une référence prouvant que si est un chemin ou une subdivision d'une griffe et est un mineur de H alors G est un sous-graphique de H ? Il est mentionné ici brièvement mais manque de référence.GHGH

Eli
la source
Le livre est disponible sur diestel-graph-theory.com
Alexander Langer
Merci Alexander. Cette version du livre ne fournit aucune référence ou preuve de la proposition, savez-vous si l'édition complète en a une ou une autre source?
Eli
2
Je me souviens d'avoir cherché une citation pour le deuxième fait que vous avez déclaré, mais je n'ai rien trouvé. La meilleure citation que je connaisse pour la première déclaration est le livre de Diestel, qui ne prouve pas la déclaration. J'attendrai de voir si quelqu'un trouve une citation. Sinon, je posterai une preuve comme réponse.
Robin Kothari
1
@Robin, à ce stade, si vous postez une preuve, cela me suffit. Existe-t-il un moyen approprié de vous attribuer si ce résultat devait être utilisé quelque part? Je ne connais pas la politique d'échange de pile ni la pratique standard.
Eli
1
En fait, la citation a déjà été discutée et résolue ici: meta.cstheory.stackexchange.com/questions/352/…
Aaron Sterling

Réponses:

13

Si G est un graphique avec un degré maximum 3 et est un mineur de H , alors G est un mineur topologique de HGHGH

GHGH

HHHGHG

GHH

HG

H1H2H2H1HGGHH

GHGH

GHHHG

Nous avions également besoin de ce résultat pour un article une fois, nous avons donc inclus une courte épreuve dans notre article. Vous pouvez trouver le résultat dans la complexité de requête quantique des propriétés de graphique fermées par des mineurs . Il est mentionné à la page 13. Cependant, ce fait est caché dans la preuve d'autre chose et n'est pas explicitement énoncé comme théorème.

Ce qui est également intéressant, c'est qu'il y a un contraire à ce théorème:

GGG

Robin Kothari
la source
1
Merci. S'il vous arrive de tomber sur une citation publiée pour ces résultats, je l'aimerais toujours, mais c'est stellaire.
Eli
Cette réponse est maintenant en vedette sur le blog communautaire.
Aaron Sterling
Bonne réponse, mais je pense que votre technique de refus des contractions de degré 1 a un défaut. Par exemple, considérons G = K_4 moins n'importe quelle arête. La contraction le long des deux sommets du degré 3 dans G produira le graphique de chemin P_3, avec le degré maximal 2. Au lieu de cela, si vous interdisez les contractions sur un bord qui seraient équivalentes à une suppression, la preuve devrait passer. Formellement, vous interdisez toute contraction entre le sommet x et y si gamma (x) \ {y} = gamma (y) \ x. Il est facile de montrer que toute contraction ne violant pas cette contrainte entraînera un nouveau sommet de degré non diminué.
RussellStewart
@ user2237635: Vous avez raison, merci.
Robin Kothari