Sobre subclases y variantes de los grafos perfectos

Mostrar todas las versiones(3)

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 p...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Bonomo, Flavia
Otros Autores: Durán, Guillermo Alfredo
Formato: Tesis doctoral publishedVersion
Lenguaje:Inglés
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2005
Materias:
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
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n3897_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n3897_Bonomo
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
topic 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
spellingShingle 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
Bonomo, Flavia
Sobre subclases y variantes de los grafos perfectos
topic_facet 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
description 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,
author2 Durán, Guillermo Alfredo
author_facet Durán, Guillermo Alfredo
Bonomo, Flavia
format Tesis doctoral
Tesis doctoral
publishedVersion
author Bonomo, Flavia
author_sort Bonomo, Flavia
title Sobre subclases y variantes de los grafos perfectos
title_short Sobre subclases y variantes de los grafos perfectos
title_full Sobre subclases y variantes de los grafos perfectos
title_fullStr Sobre subclases y variantes de los grafos perfectos
title_full_unstemmed Sobre subclases y variantes de los grafos perfectos
title_sort sobre subclases y variantes de los grafos perfectos
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2005
url https://hdl.handle.net/20.500.12110/tesis_n3897_Bonomo
work_keys_str_mv AT bonomoflavia sobresubclasesyvariantesdelosgrafosperfectos
_version_ 1782023012803936256
spelling tesis:tesis_n3897_Bonomo2023-10-02T19:54:06Z Sobre subclases y variantes de los grafos perfectos Bonomo, Flavia Durán, Guillermo Alfredo 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 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, Perfect graphs were defined by Claude Berge in 1960. A graph G is perfect whenever for every induced subgraph H of G, the chromatic number of H equals the cardinality of a maximum complete subgraph of H. Perfect graphs are very interesting from an algorithmic point of view: while determining the clique number and the chromatic number of a graph are NP-complete problems, they are solvable in polynomial time for perfect graphs. Since then, many variations of perfect graphs were defined and studied, including the class of clique-prefect graphs. A clique in a graph is a complete subgraph maximal under inclusion. A clique-transversal of a graph G is a subset of vertices meeting all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The term \\clique-perfect" was introduced by Guruswami and Pandu Rangan in 2000, but the equality of these parameters had been previously studied by Berge in the context of balanced hypergraphs. A characterization of perfect graphs by minimal forbidden subgraphs was recently proved by Chudnovsky, Robertson, Seymour and Thomas, and a polynomial time recognition algorithm for this class of graphs has been developed by Chudnovsky, Cornuéjols, Liu, Seymour and Vusković. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning cliqueperfect graphs is the complexity of the recognition problem. In this thesis, we present partial results in these directions, that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph is either a line graph, or claw-free hereditary clique-Helly, or diamond-free, or a Helly circular-arc graph. Almost all of these characterizations lead to polynomial time recognition algorithms for clique-perfection in the corresponding class of graphs. Berge defined a hypergraph to be balanced if its vertex-edge incidence matrix is balanced, that is, if it does not contain the vertex-edge incidence matrix of an odd cycle as a submatrix. In 1998, Dahlhaus, Manuel and Miller consider this concept applied to graphs, defining a graph to be balanced when its vertex-clique incidence matrix is balanced. Balanced graphs are an interesting subclass in the intersection of perfect and clique-perfect graphs. We give two new characterizations of this class, the first one by forbidden subgraphs and the second one by clique subgraphs. Using domination properties we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the stable set problem, the clique-independent set problem and the clique-transversal problem in one of these subclasses. Finally, we analyze the behavior of balanced graphs and these four subclasses under the clique graph operator. Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2005 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n3897_Bonomo

Ejemplares similares