Biclique coloreo de grafos

Mostrar todas las versiones(2)

Un k-clique-coloreo de un grafo es una asignación de k colores a sus vértices de manera que toda clique tiene al menos dos vértices con colores distintos. El problema de determinar si un grafo es k-clique coloreable es Σp 2 -Completo, aunque es más fácil para ciertas clases de grafos. En esta tesis,...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Terlisky, Pablo Ezequiel
Otros Autores:	Groshaus, Marina Esther
Formato:	Tesis de grado publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2010
Materias:	TEORIA DE GRAFOS COLOREO DE GRAFOS CLIQUE COLOREO BICLIQUE COLOREO COMPLEJIDAD DE BICLIQUE COLOREO BICLIQUES GRAFOS SPLIT GRAFOS THRESHOLD GRAFOS BLOQUE GRAFOS (W4, DART, GEM) FREE GRAPH THEORY GRAPH COLORING CLIQUE-COLORING BICLIQUE COLORING COMPLEXITY OF BICLIQUE COLORING SPLIT GRAPHS THRESHOLD GRAPHS BLOCK GRAPHS (W4, DART, GEM) FREE GRAPHS
Acceso en línea:	https://hdl.handle.net/20.500.12110/seminario_nCOM000746_Terlisky https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000746_Terlisky_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-seminario_nCOM000746_Terlisky_oai
record_format	dspace
spelling	I28-R145-seminario_nCOM000746_Terlisky_oai2025-08-20 Groshaus, Marina Esther Soulignac, Francisco Juan Terlisky, Pablo Ezequiel 2010 Un k-clique-coloreo de un grafo es una asignación de k colores a sus vértices de manera que toda clique tiene al menos dos vértices con colores distintos. El problema de determinar si un grafo es k-clique coloreable es Σp 2 -Completo, aunque es más fácil para ciertas clases de grafos. En esta tesis, definimos el problema de k-biclique-coloreo como el análogo del de k-clique-coloreo en el contexto de bicliques. Probamos que el problema de determinar si un grafo es k-biclique-coloreable es Σp 2 -Completo para k ≥ 2, y mostramos algunas clases de grafos para las que el problema está en NP o es polinomial. A k-clique-coloring of a graph is an assignment of k colors to its vertices such that every clique has at least two vertices with different colors. For k ≥ 2, the problem of kclique-coloring a graph is Σp 2 -complete, though it is easier for some graph classes. In this work, we define the k-biclique-coloring problem as the analogue of the k-clique-coloring for bicliques. We prove that the k-biclique-coloring problem is Σp 2 -complete for k ≥ 2, and show some graph classes for which the problem is in NP or polynomial. Fil: Terlisky, Pablo Ezequiel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/seminario_nCOM000746_Terlisky spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar TEORIA DE GRAFOS COLOREO DE GRAFOS CLIQUE COLOREO BICLIQUE COLOREO COMPLEJIDAD DE BICLIQUE COLOREO BICLIQUES GRAFOS SPLIT GRAFOS THRESHOLD GRAFOS BLOQUE GRAFOS (W4, DART, GEM) FREE GRAPH THEORY GRAPH COLORING CLIQUE-COLORING BICLIQUE COLORING COMPLEXITY OF BICLIQUE COLORING BICLIQUES SPLIT GRAPHS THRESHOLD GRAPHS BLOCK GRAPHS (W4, DART, GEM) FREE GRAPHS Biclique coloreo de grafos Graph biclique coloring info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000746_Terlisky_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
language	Español
orig_language_str_mv	spa
topic	TEORIA DE GRAFOS COLOREO DE GRAFOS CLIQUE COLOREO BICLIQUE COLOREO COMPLEJIDAD DE BICLIQUE COLOREO BICLIQUES GRAFOS SPLIT GRAFOS THRESHOLD GRAFOS BLOQUE GRAFOS (W4, DART, GEM) FREE GRAPH THEORY GRAPH COLORING CLIQUE-COLORING BICLIQUE COLORING COMPLEXITY OF BICLIQUE COLORING BICLIQUES SPLIT GRAPHS THRESHOLD GRAPHS BLOCK GRAPHS (W4, DART, GEM) FREE GRAPHS
spellingShingle	TEORIA DE GRAFOS COLOREO DE GRAFOS CLIQUE COLOREO BICLIQUE COLOREO COMPLEJIDAD DE BICLIQUE COLOREO BICLIQUES GRAFOS SPLIT GRAFOS THRESHOLD GRAFOS BLOQUE GRAFOS (W4, DART, GEM) FREE GRAPH THEORY GRAPH COLORING CLIQUE-COLORING BICLIQUE COLORING COMPLEXITY OF BICLIQUE COLORING BICLIQUES SPLIT GRAPHS THRESHOLD GRAPHS BLOCK GRAPHS (W4, DART, GEM) FREE GRAPHS Terlisky, Pablo Ezequiel Biclique coloreo de grafos
topic_facet	TEORIA DE GRAFOS COLOREO DE GRAFOS CLIQUE COLOREO BICLIQUE COLOREO COMPLEJIDAD DE BICLIQUE COLOREO BICLIQUES GRAFOS SPLIT GRAFOS THRESHOLD GRAFOS BLOQUE GRAFOS (W4, DART, GEM) FREE GRAPH THEORY GRAPH COLORING CLIQUE-COLORING BICLIQUE COLORING COMPLEXITY OF BICLIQUE COLORING BICLIQUES SPLIT GRAPHS THRESHOLD GRAPHS BLOCK GRAPHS (W4, DART, GEM) FREE GRAPHS
description	Un k-clique-coloreo de un grafo es una asignación de k colores a sus vértices de manera que toda clique tiene al menos dos vértices con colores distintos. El problema de determinar si un grafo es k-clique coloreable es Σp 2 -Completo, aunque es más fácil para ciertas clases de grafos. En esta tesis, definimos el problema de k-biclique-coloreo como el análogo del de k-clique-coloreo en el contexto de bicliques. Probamos que el problema de determinar si un grafo es k-biclique-coloreable es Σp 2 -Completo para k ≥ 2, y mostramos algunas clases de grafos para las que el problema está en NP o es polinomial.
author2	Groshaus, Marina Esther
author_facet	Groshaus, Marina Esther Terlisky, Pablo Ezequiel
format	Tesis de grado Tesis de grado publishedVersion
author	Terlisky, Pablo Ezequiel
author_sort	Terlisky, Pablo Ezequiel
title	Biclique coloreo de grafos
title_short	Biclique coloreo de grafos
title_full	Biclique coloreo de grafos
title_fullStr	Biclique coloreo de grafos
title_full_unstemmed	Biclique coloreo de grafos
title_sort	biclique coloreo de grafos
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2010
url	https://hdl.handle.net/20.500.12110/seminario_nCOM000746_Terlisky https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000746_Terlisky_oai
work_keys_str_mv	AT terliskypabloezequiel bicliquecoloreodegrafos AT terliskypabloezequiel graphbicliquecoloring
_version_	1843126923829444608

Biclique coloreo de grafos

Ejemplares similares