Tipus de document
Treball de fi de grauData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/227474
Más allá del teorema de Vizing
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
El Teorema de Vizing es una base fundamental para la teoría de coloración de grafos por aristas. Este teorema da una cota para el índice cromático y discierne entre los grafos simples de Clase 1 ($\chi' = \Delta$) y los de Clase 2 ($\chi' = \Delta + 1$). En este trabajo se recogen dos pruebas del mismo y algoritmos destinados a obtener $(\Delta + 1)$-coloraciones de cualquier grafo simple. La clasificación de grafos simples en Clase 1 y Clase 2 es un problema $NP$–completo, lo que descarta una caracterización simple y eficiente del caso general.
Posteriormente, generalizando a grafos multiarista se obtienen diversas cotas para el índice cromático. En este trabajo se recogen tanto cotas superiores como inferiores y las demostraciones de las mismas. A su vez se aporta un algoritmo para obtener una \[3\left\lceil \frac{\Delta(G)}{2} \right\rceil\]-coloración de cualquier multigrafo.
Quedando así definido el marco teórico para poder comprender el desarrollo de la recientemente demostrada conjetura de Goldberg–Seymour. Esta conjetura da una igualdad para el índice cromático de cualquier grafo.
Descripció
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Kolja Knauer
Matèries (anglès)
Citació
Col·leccions
Citació
JUANO DE ECHAVE, Paloma. Más allá del teorema de Vizing. [consulted: 22 of May of 2026]. Available at: https://hdl.handle.net/2445/227474