Preguntas etiquetadas con interval-graphs

Partición en gráficos de intervalos

Supongamos que hay un gráfico . Quiero probar si V puede dividirse en dos conjuntos disjuntos V 1 y V 2, de modo que las subgrafías inducidas por V 1 y V 2 sean gráficos de intervalo de unidad.G = ( V, E)sol=(V,mi)G=(V,E)VVVV1V1V_1V2V2V_2V1V1V_1V2V2V_2 Sé acerca de la completitud NP de determinar...

Límite inferior en el tamaño de subgrafos inducidos por intervalo máximo de un gráfico de -vértices

Sea un subgrafo de intervalo inducido máximo de un gráfico . Si¿Cuál es el número más pequeño de ?HHHG=(V,E)G=(V,E)G=(V,E)n=|V|n=|V|n=|V|V(H)V(H)V(H) El número es como máximo : considere un conjunto de agujeros distintos.3n/43n/43n/4444 ¿Puede ser más