Más allá del teorema de Vizing

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.