Document type
Bachelor thesisPublication date
Publication license
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/227474
Más allá del teorema de Vizing
Journal Title
Authors
Director/Tutor
Journal ISSN
Volume Title
Related resource
Abstract
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.
Description
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Kolja Knauer
Subject (English)
Citation
Collections
Citation
JUANO DE ECHAVE, Paloma. Más allá del teorema de Vizing. [consulted: 17 of June of 2026]. Available at: https://hdl.handle.net/2445/227474