Partição em gráficos de intervalo

13

Suponha que exista um gráfico . Quero testar se V pode ser particionado em dois conjuntos separados V 1 e V 2, de modo que os subgráficos induzidos por V 1 e V 2 sejam gráficos de intervalo unitário.G=(V,E)VV1V2V1V2

Eu sei sobre o NP-completude de determinar números de intervalo, mas o problema acima é diferente. Agora, na literatura, encontrei este trabalho de A. Gyárfás e D. West em gráficos de intervalos multipista, mas não tenho certeza se é relevante para o problema acima.

Qualquer citação à literatura existente sobre o problema acima ou similar seria útil. Além disso, informe-me se houver um nome formal para o problema acima.

Dibyayan
fonte
O reconhecimento de um gráfico de duas trilhas (no jornal Oeste) não é exatamente o seu problema?
Suresh Venkat
4
Eu acho que reconhecer gráficos de 2 faixas é a versão de ponta do problema.
v le

Respostas:

21

V1,V2G(V1)PG(V2)QPQPQ é não trivial (ou seja, nem todos os gráficos da classe são sem borda).

vb le
fonte