Partición libre de H

Esta es una pregunta inspirado en el problema de corte libre-H . Dado un gráfico, una partición de su vértice establece en partes tiene si no induce una copia de para todo , . $V$ $r$ $V_1, V_2, \ldots, V_r$ $H$ $G[V_i]$ $H$ $i$ $1 \leq i \leq r$

Deseo considerar la siguiente pregunta:

¿Cuál es la menor para la que existe una partición libre de en partes? $r$ $H$ $r$

Tenga en cuenta que cuando es un borde único, esto equivale a encontrar el número cromático y ya está NP completo. Me pregunto si es más fácil mostrar la integridad de NP para cualquier fijo para este problema (más fácil, en comparación con mostrarlo para un corte sin ). Incluso pensé que podría ser obvio, pero no llegué a ninguna parte. Es muy posible que me falte algo bastante sencillo, y si este es el caso, agradecería algunos consejos. $H$ $H$ $H$

graph-theory np-hardness co.combinatorics Neeldhara
fuente

Quiere decir: para todo

y para todo

, el subgrafo de

inducido por

no es isomorfo a

i

$i$

U \subseteq V_{i}

$U \subseteq V_i$

G

$G$

U

$U$

H

$H$

Jukka Suomela

Creo que la respuesta de RJK al otro problema vinculado a esto se aplica a este problema (de hecho, es mejor que al otro problema).

Tsuyoshi Ito

@ Jukka: Muy bien, lo hago. ¡Gracias por el puntero, y perdóname por ser demasiado vago (al menos por ahora) para actualizar la pregunta en consecuencia!

Neeldhara

@ Tsuyoshi: ¡Sí, y ahora también tengo una versión más elaborada de la respuesta! Sin embargo, debo decir que publiqué esto porque me encontré en la situación "I-hit-a-roadblock-while-pensando-about-X e Y-parece-un-relacionado-y-más fácil-comienzo". Solo pensé que debería compartir los detalles de Y para el resto que estaba pensando en X, y no estaba destinado principalmente a ser una solicitud de referencia :)

Neeldhara

Serge Gaspers se refirió a un antiguo artículo (Lewis) de 1980 y Yannakakis que parece muy relevante aquí.

RJK

Respuestas:

Las primeras referencias que conozco a este tipo de problema son las siguientes. Estos también se mencionan en el artículo de Cowen, Goddard y Jesurum que mencioné en el otro hilo.

Andrews y Jacobson. (1985) Sobre una generalización del número cromático. En proc. 16ª Conferencia Internacional del Sudeste sobre Combinatoria, Teoría de Gráficos e Informática (Boca Raton 1985), Congr. Numer. 47 33-48.

Cowen, Cowen y Woodall. (1986) Colores defectuosos de gráficos en superficies: particiones en subgrafías de valencia limitada. J. Teoría de grafos 10 187–195.

Harary (1985) Colorabilidad condicional en gráficos. En Graphs and Applications (Boulder 1982), Wiley – Interscience, págs. 127–136.

Harary y Jones (nee Fraughnaugh). (1985) Colorabilidad condicional II: variaciones bipartitas. En proc. Conferencia de Sundance sobre combinatoria y temas relacionados (Sundance 1985), Congr. Numer. 50 205–218.

AFAIK, todavía no hay un documento que proporcione la dicotomía explícita P / NP-c para varias opciones de H. Sin embargo, esto ha sido hecho, por Hell y Nesetril, para otro tipo de generalización del número cromático, "colorantes H ", a los homomorfismos.

RJK
fuente

Muchas gracias por su respuesta muy detallada, muy apreciada. Esa es una adición sustancial a mi lista de lectura, ¡debería mantenerme ocupado por un tiempo!

Neeldhara

Bueno, no es un problema, aunque, como mencioné antes, además del documento de JGT, es bastante difícil rastrearlos. (De hecho, debo admitir que aún no he tenido mucho éxito, a pesar de haber tenido acceso a muchas bibliotecas universitarias canadienses). En cualquier caso, el artículo de Cowen, Goddard y Jesurum es probablemente el más relevante y responde a su pregunta / la de Moron para H siendo una estrella fija, incluso restringida a gráficos planos. Probablemente las clases abiertas más bonitas (¿creo?) De H para hundir los dientes serían ciclos o camarillas.

RJK

En "La partición del vértice en propiedades hereditarias aditivas fijas es NP-duro", Alastair Farrugia demuestra que si $F_1$ y $F_2$ son dos familias de gráficos conectados, entonces el problema de dividir un gráfico en dos partes, una de las cuales es $F_1$ libre y el otro $F_2$ -free es NP-hard, excepto cuando ambos $F_1$ y $F_2$ consisten en el borde único.

(Sin F = {para todo H en F, sin H})

Ver www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf

Aravind
fuente