Coloración en triangulaciones

Esteban Pascual, Guillermo (2017). Coloración en triangulaciones. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Descripción

Título: Coloración en triangulaciones
Autor/es:
  • Esteban Pascual, Guillermo
Director/es:
  • Hernández Peñalver, Gregorio
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado de Matemáticas e Informática
Fecha: Junio 2017
Materias:
Palabras Clave Informales: 3-coloring; Maximal outerplanar graph;Steinberg's Conjecture;NP-problems; 3-coloración; Grafo periplano maximal; Conjetura Steinberg; Problemas NP
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

Some of the most studied problems in Graph Theory are those referring to the coloring of the graph, being one of the most famous the Three Color Problem. A color set D for a graph G is said to be a 3-coloring if adjacent vertex has a different color of D making the graph 3-coloreable. It seems to be obvious to wonder which graphs are 3-coloreable. Nevertheless, the problem of finding sufficient conditions for a graph to be 3-coloreable in a general graph has been shown by L. Stockmayer in 1979 in his book “Planar 3-colorability is polynomial complete" to be NP-complete. That is why different bounds for x(G) are studied and stated for both arbitrary graphs and for those with a particular structure. Nonetheless, the interest in this parameter is not only to establish new bounds, but also once the bounds have been obtained, either upper or bottom, this naturally brings us the question of knowing if there exists any graph which verifies the equality. Throughout these months, the results achieved about the 3-coloring problem for arbitrary graphs have been studied and, specifically, those results referring to the variants of the 3-coloration problem attending to the sum of colors, the distance between vertex or the parity among the apparition of certain color. This research has been performed not only from a combinatorial point of view but also from an algorithmic point of view and has been restricted to a particular kind of graph, known as maximal outerplanar graphs and denoted by its acronym as MOP's, graph of high importance in both the field of chemistry and polygon triangulations. This project has a double purpose: on the one hand, it seeks to collect those results in the literature which have been observed to be more significant in a review paper or sur- vey; on the other hand, it seeks to established tight combinatorial bounds for some variants of the 3-coloration concept for any n-vertex maximal outerplanar graph. Thus, as main contributions, we will prove several new tight combinatorial bounds for the following variants of coloration concept attending to the sum of the colors been used: sum-coloring, as well as the following variants attending to the existence of a rainbow path: rainbow coloring.---ABSTRACT---Algunos de los problemas más estudiados en Teoría de Grafos son aquellos problemas que hacen referencia a la coloración del mismo, siendo uno de los más clásicos el problema de los Tres Colores. Un conjunto D de colores de un grafo G se dice que es una 3-coloración si vértices adyacentes tienen un color distinto de D haciendo el grafo 3-coloreable. Parece entonces obvio preguntarse qué grafos son 3-coloreables. Sin embargo, ya en 1979 L. Stockmayer en su artículo “Planar 3-colorability is polynomial complete" probó que este problema es NP-completo. Es por ello por lo que se estudian y establecen cotas para x(G) para el caso de grafos cualesquiera o para grafos con cierta estructura. Sin embargo, el interés en este parámetro no sólo radica en establecer una cota, sino que una vez obtenida dicha cota, ya sea superior o inferior, quedaría comprobar la existencia de algún grafo que verifique la igualdad. A lo largo de estos meses de trabajo, se han estudiado los resultados obtenidos hasta la fecha en el problema de la 3-coloración de grafos en general y más concretamente sobre aquellas variantes de 3-coloración que atienden a la suma de los colores, la distancia entre vértices o la paridad en la aparición de cierto color. Este estudio se ha llevado a cabo tanto desde el punto de vista combinatorio como algorítmico y se ha restringido a un tipo particular de grafos, conocidos como grafos periplanos maximales y de nominados a partir de ahora por sus siglas en inglés MOP's (maximal outerplanar graphs), grafos de gran importancia tanto en el ámbito de la química como en el de triangulaciones de polígonos. Con este proyecto se persigue un doble objetivo: por un lado, se pretende recopilar aque- llos resultados más significativos de la bibliografía en un artículo de tipo "survey"; por otro, obtener nuevos resultados sobre variantes de dominación para MOP's. Así, como aporte de nuestro trabajo, probaremos nuevas cotas que se han establecido tanto para los criterios de 3-coloración que atienden a la suma de colores utilizados en la coloración: sum-coloring, como para variantes que atienden a la existencia de caminos irisados en la coloración del grafo: coloración irisada.

Más información

ID de Registro: 47115
Identificador DC: http://oa.upm.es/47115/
Identificador OAI: oai:oa.upm.es:47115
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 02 Jul 2017 08:48
Ultima Modificación: 02 Jul 2017 08:48
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM