Fundamentos de coloreado de grafos y teoría de Ramsey

Abstract

El contenido de este trabajo está dividido en cuatro partes. La primera constituida por fundamentos sobre grafos, que contiene definiciones y resultados básicos para el desarrollo del texto. En segundo lugar se presentan definiciones y cotas para el problema del número cromático, éste capítulo se amplía en los Apéndices A y B, que se refieren al Polinomio Cromático y al Teorema de Los Cuatro Colores del cual se hace una presentación informal e histórica. Posteriormente, se dedica la tercera parte al Teorema de Ramsey y algunas aplicaciones, para lo cual se presenta como preámbulo el Principio del Palomar. Se termina con un capítulo sobre el cálculo de algunas cotas y números de Ramsey, de lo cual se muestra una tabla actualizada en el Apéndice C.