Esta é uma questão inspirado pelo problema corte livre-H . Dado um gráfico, uma partição de seu conjunto de vértices em r partes V 1 , V 2 , … , V r é livre de H se G [ V i ] não induzir uma cópia de H para todos os i , 1 ≤ i ≤ r .
Desejo considerar a seguinte pergunta:
Qual é o menor para o qual existe uma partição livre de H em partes r ?
Observe que, quando é uma aresta única, isso equivale a encontrar o número cromático e já está NP-completo. Gostaria de saber se é mais fácil mostrar a completude de NP para qualquer H fixo para esse problema (mais fácil, em comparação com mostrá-lo para o corte sem H ). Eu até pensei que fosse óbvio, mas não cheguei a lugar algum. É perfeitamente possível que eu esteja perdendo algo bastante direto e, se for esse o caso, eu apreciaria algumas dicas!
fonte
Respostas:
As primeiras referências que conheço para esse tipo de problema são as seguintes. Estes também são mencionados no artigo de Cowen, Goddard e Jesurum que mencionei no outro tópico.
Andrews e Jacobson. (1985) Em uma generalização de número cromático. Em Proc. 16ª Conferência Internacional do Sudeste de Combinatória, Teoria dos Gráficos e Computação (Boca Raton 1985), Congr. Numer. 47 33-48.
Cowen, Cowen e Woodall. (1986) Colorações defeituosas de gráficos em superfícies: Partições em subgráficos de valência limitada. J. Teoria dos Gráficos 10 187–195.
Harary. (1985) Colorabilidade condicional em gráficos. In Graphs and Applications (Boulder, 1982), Wiley – Interscience, pp. 127–136.
Harary e Jones (nee Fraughnaugh). (1985) Colorabilidade condicional II: variações bipartidas. Em Proc. Conferência de Sundance sobre Combinatória e Temas Relacionados (Sundance 1985), Congr. Numer. 50 205-218.
AFAIK, ainda não há um documento que dê a dicotomia explícita P / NP-c para várias opções de H. Isso foi feito, no entanto, por Hell e Nesetril, para outro tipo de generalização do número cromático, "cores H ", aos homomorfismos.
fonte
(Livre de F = {para todo H em F, livre de H})
Consulte www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf
fonte