# metadata.dc.description[].value
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Kolja Knauer

# metadata.dc.description.abstract[].value
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.

# metadata.dc.rights[].value
cc-by-nc-nd (c) Paloma Juano de Echave, 2025

# metadata.dc.source[].value
Treballs Finals de Grau (TFG) - Matemàtiques