Entendendo o teorema menor do gráfico

9

Esta pergunta é dupla e é principalmente orientada a referências:

  1. Existe algum lugar onde as principais intuições para provar o teorema menor do gráfico são dadas, sem entrar muito nos detalhes? Sei que a prova é longa e difícil, mas certamente deve haver idéias-chave que possam ser comunicadas de maneira mais fácil.

  2. Existem outras relações nos gráficos que podem ser mostradas como quase-ordens, talvez de uma maneira mais simples do que na relação menor? (obviamente não estou interessado em resultados triviais aqui, como comparar tamanhos). Gráficos direcionados também estão no escopo da pergunta.

Denis
fonte
11
Estou especialmente interessado na questão 1 ... Não existe um esquema de prova compreensível do teorema de Robertson-Seymour?
Denis

Respostas:

8

O livro a seguir aborda algum material relacionado à prova do teorema menor do gráfico (capítulo 12).

Reinhard Diestel: Graph Theory, 4ª edição, Textos de Pós-Graduação em Matemática 173.

O autor declara: "[...] temos que ser modestos: da prova real do teorema menor, este capítulo transmitirá apenas uma impressão muito grosseira. No entanto, como nos resultados mais verdadeiramente fundamentais, a prova provocou a desenvolvimento de métodos de interesse e potencial bastante independentes ".

Uma versão eletrônica do livro pode ser visualizada online. http://diestel-graph-theory.com/

Hermann Gruber
fonte
7

Para a questão (2): as relações subgráficas e subgráficas induzidas dão origem a ordens quase quasi em algumas classes restritas de gráficos. Uma das principais referências de um artigo de G. Ding, subgráficos e quase ordenada , J. Graph Theory, 16: 489–502, 1992, doi: 10.1002 / jgt.3190160509 . O papel

  1. mostra que ambos os pedidos produzem wqos na classe de gráficos com comprimentos de caminho limitados e
  2. ainda mais interessante, caracteriza exatamente as classes hereditárias de gráficos para as quais a ordem dos subgráficos se torna um wqo (a classe deve conter apenas finitamente muitos ciclos e "gráficos H").

Mais resultados no caso da ordenação subgráfica induzida podem ser encontrados neste artigo recente do arXiv por A. Atminas, V. Lozin e I. Razgon.

Sylvain
fonte
11
O artigo a seguir também pode ser interessante a esse respeito: MR Fellows, D. Hermelin, FA Rosamond: Ordens de Quase-Ordens em Subclasses de Gráficos de Largura de Árvore Limitada e suas Aplicações Algorítmicas. Algorithmica 64 (1): 3-18, 2012
Hermann Gruber