Saltar para o conteúdo

Teorema de Robertson–Seymour

Origem: Wikipédia, a enciclopédia livre.

Na teoria dos grafos, o teorema de Robertson–Seymour (também chamado teorema menor dos grafos[1]) estabelece que os grafos não direcionados, parcialmente ordenados pelo relacionamento do grafo menor, formam um quase-bem-ordenado.[2]

Referências

  1. Bienstock, Daniel; Langston, Michael A. (1995), «Algorithmic implications of the graph minor theorem», Network Models (PDF), Handbooks in Operations Research and Management Science, 7, pp. 481–502, doi:10.1016/S0927-0507(05)80125-2 
  2. Robertson, Neil; Seymour, Paul (2004), «Graph Minors. XX. Wagner's conjecture», Journal of Combinatorial Theory, Series B, 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001