Graph minor
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.
Wikipage disambiguates
Aanderaa–Karp–Rosenberg conjectureAlbertson conjectureApex graphApollonian networkBaker's techniqueBetter-quasi-orderingBiased graphBidimensionalityBojan MoharBorůvka's algorithmBoxicityBranch-decompositionBratteli–Vershik diagramCactus graphClique-sumClique (graph theory)Clique problemColin de Verdière graph invariantColor-codingCombinatorics: The Rota WayComplete bipartite graphComplete graphConflict-free coloringConstructive proofCourcelle's theoremCycle basisDiamond graphEdge contractionErdős–Pósa theoremErik DemaineEulerian matroidForbidden graph characterizationFriedman's SSCG functionFulkerson PrizeGNRS conjectureGalactic algorithmGlossary of graph theoryGraph-minorGraph amalgamationGraph coloring
Link from a Wikipage to another Wikipage
primaryTopic
Graph minor
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.
has abstract
In der Graphentheorie sind Min ...... rem von Robertson und Seymour.
@de
In graph theory, an undirected ...... l minors and immersion minors.
@en
La notion de mineur d'un graph ...... ial Theory entre 1983 et 2011.
@fr
Minor grafu je rozšířením pojmu podgrafu.
@cs
Στη θεωρία γραφημάτων, ένα μη- ...... λάσσων γραφήματα συγκέντρωσης.
@el
В теорії графів неорієнтований ...... ічні мінори і занурені мінори.
@uk
Минор в теории графов — граф д ...... е миноры и погружённые миноры.
@ru
在图论中,如果无向图H可以通过图G删除边和顶点或收缩边得到, ...... 在多项式时间内被识别。其他涉及到图子式的定理和猜想包括、等。
@zh
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,020,380,615
Link from a Wikipage to another Wikipage
title
Graph Minor
@en
urlname
GraphMinor
@en
wikiPageUsesTemplate
hypernym
comment
In der Graphentheorie sind Min ...... rem von Robertson und Seymour.
@de
In graph theory, an undirected ...... recognized in polynomial time.
@en
La notion de mineur d'un graph ...... ial Theory entre 1983 et 2011.
@fr
Minor grafu je rozšířením pojmu podgrafu.
@cs
Στη θεωρία γραφημάτων, ένα μη- ...... θε γράφημα ιδιότητας το οποίο
@el
В теорії графів неорієнтований ...... пізнана за поліноміальний час.
@uk
Минор в теории графов — граф д ...... удалениях и стягивании рёбер.
@ru
在图论中,如果无向图H可以通过图G删除边和顶点或收缩边得到, ...... 在多项式时间内被识别。其他涉及到图子式的定理和猜想包括、等。
@zh
label
Graph minor
@en
Mineur (théorie des graphes)
@fr
Minor (Graphentheorie)
@de
Minor (teorie grafů)
@cs
Ελάσσων γράφος
@el
Минор графа
@ru
Мінор графа
@uk
图子式
@zh
그래프 마이너
@ko