Sobre subclases y variantes de los grafos perfectos

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2005

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

eng

Temas:

GRAFO CLIQUE - GRAFOS ARCO-CIRCULARES HELLY - GRAFOS BALANCEADOS - GRAFOS CLIQUE-HELLY HEREDITARIOS SIN K1,3 - GRAFOS CLIQUE-PERFECTOS - GRAFOS DE LINEA - GRAFOS K-PERFECTOS - GRAFOS PERFECTOS - GRAFOS SIN DIAMANTES - BALANCED GRAPHS - CLIQUE GRAPH - CLIQUE-PERFECT GRAPHS - DIAMOND-FREE GRAPHS - HELLY CIRCULAR-ARC GRAPHS - HEREDITARY CLIQUE-HELLY CLAW-FREE GRAPHS - K-PERFECT GRAPHS - LINE GRAPHS - PERFECT GRAPHS

Descripción:

Los grafos perfectos fueron definidos por Claude Berge en 1960. Un grafo G es perfecto cuando para todo subgrafo inducido H de G, el número cromático de H es igual al tamaño de un subgrafo completo máximo de H. Los grafos perfectos son de gran interés desde el punto de vista algoritmo: si bien los problemas de determinar la clique máxima y el número cromático de un grafo son NP-completos, éstos se resuelven en tiempo polinomial para grafos perfectos. Desde entonces, fueron definidas y estudiadas gran cantidad de variantes de los grafos perfectos. Entre ellas, los grafos clique-perfectos. Una clique en un grafo es un subgrafo completo maximal con respecto a la inclusión. Un transversal de las cliques de un grafo G es un subconjunto de vértice que interseca a todas las cliques de G. Un conjunto de cliques independientes es un conjunto de cliques disjuntas dos a dos. Un grafo G es clique-perfecto si el tamaño de un transversal de las cliques mínimo coincide con el de un conjunto de cliques independientes máximo, para cada subgrafo inducido de G. El término "clique-perfecto" fue introducido por Guruswami y Pandu Rangan en 2000, pero la igualdad de esos parámetro fue estudiada previamente por Berge en el contexto de hipergrafos balanceados. En 2002, Chudnovsky, Robertson, Seymour y Thomas demostraron una caracterización de los grafos perfectos por subgrafos prohibidos minimales, cerrando una conjetura abierta durante 40 años. También durante el año 2002 fueron presentados dos trabajos, uno de ellos de Chudnovsky y Seymour, y el otro de Cornuéjols, Liu y Vuskovic, que mostraban que el reconocimiento de esta clase era polinomial, resolviendo otro problema abierto formulado mucho tiempo atrás. La lista de subgrafos prohibidos minimales para la clase de grafos clique-perfectos no se conoce aún, y También es una pregunta abierta la complejidad del problema de reconocimiento. En esta tesis presentamos resultados parciales en estas direcciones, es decir, caracterizamos los grafos cliqueperfectos por subgrafos prohibidos minimales dentro de ciertas clases de grafos, a saber,

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n3897_Bonomo