El número aproximado de coloraciones parece ser fácil en gráficos con exclusión menor utilizando el algoritmo de Jung / Shah. ¿Cuáles son otros ejemplos de problemas que son difíciles en gráficos generales pero fáciles en gráficos excluidos menores? Actualización 10/24 Parece seguir los...
A continuación, MSO denota la lógica monádica de segundo orden de los gráficos con cuantificaciones de conjuntos de vértices y conjuntos de bordes. Sea una familia cerrada menor de gráficos. Se deduce de Robertson y de Seymour gráfico teoría menor que F se caracteriza por una lista finita H 1 , H...
Me gustaría saber si hay bibliotecas de gráficos gratuitas para probar si existe un conjunto específico de menores en un gráfico
El ancho de árbol juega un papel importante en los algoritmos de FPT, en parte porque muchos problemas están parametrizados por FPT por el ancho de árbol. Una noción relacionada, más restringida, es la de ancho de ruta. Si un gráfico tiene un ancho de ruta , también tiene un ancho de árbol como...
Esta pregunta es similar a una de mis preguntas anteriores. Se sabe que es un menor prohibido para gráficos de ancho de árbol como máximo t .Kt+2Kt+2K_{t+2}ttt ¿Existe una familia infinita de gráficos bien parametrizados e infinitos (que no sean gráficos completos y gráficos de cuadrícula) que...
Es bien sabido que y son menores prohibidos para gráficos planos. Hay cientos de menores prohibidos para gráficos incrustados en un toro. El número de menores prohibidos para gráficos incrustados en la superficie del género g es una función exponencial de g . Mi pregunta es la...
Los gráficos tienen . Dichos gráficos pueden descomponerse en componentes , que se sabe que son componentes planos o .K3 , 3K3,3K_{3,3}K5 5K5 5K_5 ¿Existe una descomposición tan "agradable" de los gráficos del género uno? En su trabajo seminal sobre gráficos menores, Roberston y Seymour...
Considere el siguiente problema. Entrada: Un gráfico no dirigido . Salida: Un gráfico H que es un menor de con la densidad de borde más alta entre todos los menores de , es decir, con la relación más alta.G=(V,E)G=(V,E)G=(V,E)HHHGGGGGG|E(H)|/|V(H)||E(H)|/|V(H)||E(H)|/|V(H)| ¿Se ha estudiado este...
Si es un gráfico con el máximo grado 3 y es un menor de H , entonces es un menor topológica de .solGGHHHHsolGGHHH Wikipedia cita este resultado de la "teoría de grafos" de Diestel. Está listado como la Proposición 1.7.4 en la última versión del libro. El libro carece de prueba o cita. ¿Se conoce...
Deje que sea un ciclo con cuatro vértices. Para un gráfico arbitrario con vértices y m aristas digamos , ¿cuántos existen? ¿Hay un límite inferior para esto?C4C4C_4GGGnnnm>nn−−√m>nnm>n\sqrt
Dejemos que kkk sea fijo, y que GGG sea un gráfico (conectado). Si no me equivoco, se deduce del trabajo de Bodlaender [1, Teorema 3.11] que si el ancho de árbol de GGG es aproximadamente de al menos 2k32k32k^3 , entonces GGG contiene una estrella K1,kK1,kK_{1,k} como menor. ¿Podemos hacer que...
El teorema de Courcelle establece que cada propiedad de gráfico definible en la lógica monádica de segundo orden se puede decidir en tiempo lineal en gráficos de ancho de árbol acotado . Este es uno de los metateoremas algorítmicos más conocidos. Motivado por el teorema de Courcelle, hice la...
El teorema de Robertson-Seymour dice que cualquier familia GG\mathcal G de gráficas menores cerradas puede caracterizarse por un número finito de menores prohibidos. ¿Existe algún algoritmo que para una entrada GG\mathcal G dé salida a los menores prohibidos o es indecidible? Obviamente, la...
Me dan un gráfico con un ancho de árbol k y un grado arbitrario, y me gustaría encontrar un subgrafo H de G (no necesariamente un subgrafo inducido) de modo que H tenga un grado constante y su ancho de árbol sea lo más alto posible. Formalmente, mi problema es el siguiente: habiendo elegido un...
Esta pregunta es doble y está principalmente orientada a referencias: ¿Hay algún lugar donde se den las intuiciones principales para probar el teorema menor del gráfico, sin entrar demasiado en los detalles? Sé que la prueba es larga y difícil, pero seguramente debe haber ideas clave que puedan...
Vamos ser un parámetro gráfico (ex. De diámetro, número de dominación, etc)sss Una familia de gráficos tiene la propiedad s -treewidth si hay una función f tal que para cualquier gráfico G ∈ F , el ancho de árbol de G es como máximo f ( s ) .FF\mathcal{F}sssFffG ∈ FG∈FG\in...
Definición: Una " cadena " es un gráfico múltiple obtenido a partir de una ruta de longitud al duplicar cada borde.kkkkkk Tenga en cuenta que el número de rutas entre dos puntos finales de una cadena eskkk2k.2k.2^k. Pregunta: Sea un gráfico simple en n nodos y sea y dos nodos de Suponga que el...
Thor Johnson, et al, en su artículo: Ancho de árbol dirigido , introdujeron una definición para la cuadrícula dirigida , y conjeturaron:JkJkJ_k Para cada entero k existe un entero N tal que cada dígrafo con un ancho de árbol N o más tiene un isomorfo menor a J k