Número acromático de gráficas gramíneas bipartitas

Abstract

En este trabajo estudiamos diversas propiedades de las gráficas gramíneas bipartitas, enfocándonos en particular en las coloraciones completas y el número acromático de las mismas. En el capítulo 1, presentamos al lector los conceptos preliminares más importantes para el desarrollo de éste trabajo. En el capíutlo 2, introducimos una clasificación de las gramíneas bipartitas en varias familias, y presentamos varias propiedades relacionadas con la estructura de estas familias, en particular, mostramos dos resultados importantes: una caracterización de un grupo de gramíneas bipartitas en términos de acoplamientos y la relación que el mismo grupo guarda con la familia de torneos regulares. También exploramos el problema de reconocer gráficas gramíneas en estas familias y presentamos un programa entero y un algoritmo que resuelven el problema. En cuanto a problemas de coloración, en el capítulo 3, damos una cota superior, que es justa, para el número acromático de una familia de gramíneas bipartitas y clasificamos las coloraciones completas que alcanzan dicha cota. Estudiamos algunas de las coloraciones completas mencionadas y exhibimos condiciones necesarias y condiciones suficientes para la existencia de estas coloraciones. Así mismo, presentamos técnicas para obtener y extender coloraciones completas en las gráficas de interés.