El ISGCI enumera más de 1100 clases de gráficos. Para muchos de estos sabemos si el CONJUNTO INDEPENDIENTE se puede decidir en tiempo polinómico; a veces se denominan clases IS-easy . Me gustaría compilar una lista de clases máximas IS-easy. Estas clases juntas forman el límite de la trazabilidad...
Una garra es un K1,3K1,3K_{1,3} . Un algoritmo trivial detectará una garra en el tiempo O(n4)O(n4)O(n^4) . Se puede hacer en O(nω+1)O(nω+1)O(n^{\omega+1}) , donde ωω\omega es el exponente de la multiplicación de matriz rápida, de la siguiente manera: tome el subgrafo inducido por N[v]N[v]N[v] para...
Los gráficos sin X son aquellos que no contienen ningún gráfico de X como un subgrafo inducido. Un hoyo es un ciclo con al menos 4 vértices. Un agujero impar es un agujero con un número impar de vértices. Un antiagujero es el complemento de un agujero. Los gráficos libres de (agujero impar,...
El problema del ciclo hamiltoniano (HC) consiste en encontrar un ciclo que atraviese todos los vértices en un gráfico no dirigido dado. El problema del vendedor ambulante (TSP) consiste en encontrar un ciclo que atraviese todos los vértices en un gráfico ponderado de borde dado y minimice la...
Deje y denote por G k el conjunto de todos los gráficos que se pueden incrustar en una superficie del género k de modo que todos los vértices estén situados en la cara externa . Por ejemplo, G 0 es el conjunto de gráficos de plano exterior. ¿Puede el ancho de árbol de los gráficos en G k estar...
Está formulado extendiendo los gráficos de umbral . Dado un gráfico de umbral , donde C es la camarilla y I es el conjunto independiente, mi extensión es como sigue: Cada vértice v ∈ I puede ser reemplazado por un nuevo clique K v tal que los vértices de K v tienen el mismos vecinos de v...
Estoy tratando de encontrar un gráfico con esas propiedades para mis estudios, pero desafortunadamente no puedo encontrar ese gráfico. ¿Alguien sabe si existe ese gráfico, o por qué es imposible
Dejar solsolG ser un gráfico que es la unión disjunta de una camarilla y un conjunto independiente, es decir G =Knorte1+Knorte2¯¯¯¯¯¯¯¯=Knorte1+yonorte2.sol=Knorte1+Knorte2¯=Knorte1+yonorte2.G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . La clase de gráfico de todos estos gráficos se...
¿Existe un problema gráfico de -completo natural , que sigue siendo N P -completo incluso cuando está restringido a cualquier clase de gráfico reconocible en tiempo polinómico? Para evitar casos degenerados, consideremos solo clases de gráficos densos , en los que el número de gráficos no...