Trabajo Fin de Máster
Polinomio cromático. Introducción a la coloración robusta
Autor/es | Vargas Magán, Joaquín Eloy |
Director | Garijo Royo, Delia
![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I |
Fecha de publicación | 2020-02-01 |
Fecha de depósito | 2021-07-06 |
Titulación | Universidad de Sevilla. Doble Máster MAES-MUM |
Resumen | This work is framed within the eld of Graph Theory, speci cally in the area of graph
coloring. Our main objective has been to develop an algebraic study on the chromatic
polynomial, which was introduced by Birkho in ... This work is framed within the eld of Graph Theory, speci cally in the area of graph coloring. Our main objective has been to develop an algebraic study on the chromatic polynomial, which was introduced by Birkho in 1912 in an attempt to demonstrate the famous four-color problem. This polynomial, initially de ned in terms of counting colorings, has been since intensively studied due to the great amount of information that contains on its associated graph. In addition, as a future project, we propose the extension of this idea of counting colorings to the robust coloring model, which is attracting much attention because of its great applicability. For this reason, as an essential previous step, we also study this coloring model. This memory is structured as follows. In Chapter 1 we present an introduction to Graph Theory, going into special detail for classic graph coloring, with the objective that this chapter supports the reader for a correct understanding of this work. Chapter 2 is the main part of the work, dedicated to the chromatic polynomial; it is a broad algebraic study that begins with the intuitive idea that the polynomial captures, and encompass from basic properties to results on its strength to univocally determine the graph to which it is associated. Finally, in Chapter 3, we introduce the robust coloring model, explain some of its applications and carry out a study that includes, among others, algorithmic and complexity aspects. Both Chapter 2 and Chapter 3 conclude with a section of open problems, which we believe that may be of interest to the reader. Este trabajo se enmarca en el área de Teoría de Grafos, en concreto en el ámbito de las coloraciones asociadas a grafos. Nuestro objetivo principal ha sido realizar un estudio de carácter algebraico sobre el polinomio ... Este trabajo se enmarca en el área de Teoría de Grafos, en concreto en el ámbito de las coloraciones asociadas a grafos. Nuestro objetivo principal ha sido realizar un estudio de carácter algebraico sobre el polinomio cromático, que fue introducido por Birkhoff en 1912 en un intento de demostración del conocido Problema de los Cuatro Colores. Este polinomio, definido inicialmente en términos de contar coloraciones, ha sido desde entonces ampliamente estudiado por la gran información que proporciona sobre el grafo al que está asociado. Además, como proyecto futuro, nos planteamos la extensión de esta idea de contar coloraciones al modelo de coloración robusta, que despierta mucho interés debido a su gran aplicabilidad. Es por ello que, como paso previo imprescindible, también estudiamos este modelo de coloración. Esta memoria está estructurada de la siguiente forma. En el Capítulo 1 presentamos una introducción a la Teoría de Grafos, entrando en especial detalle en la coloración clásica de grafos, con el objetivo de que este capítulo sirva de apoyo al lector para la correcta comprensión del trabajo. El Capítulo 2 es la parte central del trabajo, dedicada al polinomio cromático; es un estudio algebraico amplio que se inicia con la idea intuitiva que captura el polinomio y abarca desde propiedades básicas a resultados sobre su capacidad de determinar unívocamente al grafo al cual está asociado. Por último, en el Capítulo 3, definimos el modelo de coloración robusta, explicamos algunas de sus aplicaciones y realizamos un estudio que incluyen, entre otros, aspectos algorítmicos y de complejidad. Tanto el Capítulo 2 como el Capítulo 3 concluyen con una sección de problemas abiertos que consideramos que pueden ser de interés para el lector. |
Cita | Vargas Magán, J.E. (2020). Polinomio cromático. Introducción a la coloración robusta. (Trabajo Fin de Máster Inédito). Universidad de Sevilla, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Vargas magán, Joaquín Eloy.pdf | 1.896Mb | ![]() | Ver/ | |