Partição livre de H

13

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 .VrV1,V2,,VrHG[Vi]Hi1ir

Desejo considerar a seguinte pergunta:

Qual é o menor para o qual existe uma partição livre de H em partes r ?rHr

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! HHH

Neeldhara
fonte
2
Você quer dizer: para todo e para todos U V i , o subgrafo de G induzido por U não é isomórfico para H ? EuvocêVEuGvocêH
Jukka Suomela
Eu acho que a resposta do RJK para o outro problema vinculado a isso se aplica a esse problema (na verdade, melhor do que ao outro problema).
Tsuyoshi Ito
@Jukka: Sim, eu faço. Obrigado pelo ponteiro, e me perdoe por ser muito preguiçoso (pelo menos por enquanto) para atualizar a pergunta de acordo!
Neeldhara 04/04/10
@Tsuyoshi: Sim, e agora tenho uma versão mais elaborada da resposta aqui também! No entanto, devo dizer que postei isso porque me encontrei na situação "eu bati um obstáculo enquanto pensava em X e Y parece um começo relacionado e fácil". Eu só pensei que deveria compartilhar os detalhes de Y para o resto que estavam pensando em X, e não foi destinado principalmente para ser um pedido de referência :)
Neeldhara
Serge Gaspers se referiu a um artigo antigo (1980) de Lewis e Yannakakis que parece muito relevante aqui!
RJK

Respostas:

5

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.

RJK
fonte
Muito obrigado pela sua resposta muito detalhada - muito apreciada. Essa é uma adição substancial à minha lista de leituras, ela deve me manter ocupada por um tempo!
Neeldhara 04/04/10
Bem, isso não é um problema, embora, como mencionei antes, além do artigo da JGT, seja muito difícil encontrá-los. (De fato, devo admitir que ainda não consegui muito, apesar de ter tido acesso a muitas bibliotecas universitárias canadenses.) De qualquer forma, o artigo de Cowen, Goddard e Jesurum é provavelmente o mais relevante e responde à sua pergunta de Moron para H sendo uma estrela fixa, mesmo restrita a gráficos planares. Provavelmente, as melhores classes abertas (eu acho?) De H para afundar os dentes seriam ciclos ou panelinhas.
RJK
5

F1F2F1F2F1F2

(Livre de F = {para todo H em F, livre de H})

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

Aravind
fonte