La Teoría de Gráficas es la rama de las Matemáticas Discretas encargada del estudio de los objetos matemáticos conocidos como gráficas. Una gráfica G es una pareja ordenada de conjuntos ajenos (V;E) tal que E es un conjunto de parejas no ordenadas de elementos de V . Llamamos a V el conjunto de vértices de G y a E el conjunto de aristas de G. Si dos elementos de V forman una pareja que está en el conjunto E, decimos que estos son adyacentes. Con frecuencia, las gráficas son representadas con un dibujo en el que los vértices aparecen como puntos o pequeños círculos y las aristas como líneas que unen a los vértices adyacentes.
En esta tesis trabajamos con un tipo particular de gráficas conocidas como cográficas, que pueden ser caracterizadas de múltiples maneras. Una de ellas es que son las gráficas que no tienen a la trayectoria de 4 vértices, P4, como subgráfica inducida. Un problema clásico en la Teoría de Gráficas es la coloración de gráficas que consiste en determinar si los vértices de una gráfica se pueden etiquetar con un número determinado de etiquetas diferentes, también llamadas colores, de forma tal que, si dos vértices son adyacentes, estos tienen etiquetas diferentes. Una generalización de las coloraciones de gráficas son las particiones matriciales, que consisten en determinar si los vértices de una gráfica se pueden etiquetar con un número determinado de etiquetas diferentes de manera tal que los vértices con la misma etiqueta cumplan con una propiedad de homogeneidad. En esta tesis abordamos un problema de particiones matriciales. Estudiamos a las clases de cográficas que se definen de la siguiente manera. Dado i, un entero mayor o igual a uno, la clase Mi es la clase de las cográficas cuyo conjunto de vértices acepta una partición en i partes tal que cada parte induce una gráfica multipartita completa. La clase M1, que es la clase de las cográficas multipartitas completas, ha sido ampliamente estudiada. Sin embargo, las clases Mi para valores de i mayores a uno no han sido estudiadas con anterioridad. Nuestra investigación tiene como base el estudio de la clase M2, para el cuál tomamos como guía la investigación realizada sobre las cográficas polares. Caracterizamos a la clase M2 a través de su conjunto de obstrucciones mínimas, presentamos un algoritmo para reconocer a sus elementos y un algoritmo certificador y estudiamos a un conjunto de subclases de esta clase a las que llamamos clases (α; β)-M2. De igual manera, caracterizamos a la clase M3 a través de su conjunto de obstrucciones mínimas y proporcionamos dos familias de obstrucciones mínimas para cualquier clase Mi.
Abstract
Graph Theory is the branch of Discrete Mathematics that studies the mathematical structures known as graphs. A graph G is an ordered pair of disjoint sets (V;E) such that E is a set of unordered pairs of elements of V . We call V the set of vertices of G and E the set of edges of G. If an element of E contains two vertices, we say that those vertices are adjacent.
In this thesis, we work with a particular kind of graphs known as cographs, that can be characterized in several ways. One of this ways is that cographs are the graphs that does not contain the path on 4 vertices, P4, as an induced subgraph. A clasic problem in Graph Theory is graph coloring, which consists in deciding if it is possible to label the vertices of a graph with a given number of different labels, also known as colors, in a way such that if two vertices are adjacent, then those two vertices have different labels. A generalization of the graph coloring problem is the matrix partition problem, which consists in deciding if the vertices of a graph can be labeled with a given number of labels in a way such that vertices with the same label satisfy a homogeneity property. In this thesis we address a problem of matrix partitions. We study the classes of cographs defined in the following way. Given an integer i greater than or equal to one, the class Mi is the class of the cographs whose set of vertices accepts a partition in i parts such that each part induces a multipartite complete graph. The class M1, which is the class of multipartite complete cographs, has been widely studied. However, the classes Mi for values of i greater than one have not been previously studied. The base of our research is the study of the class M2. For this study, we use the research done about polar cographs as guide. We characterize the class M2 through its set of minimal obstructions, we present an algorithm to recognize its elements and a certifying algorithm. We also study a set of subclasses of the class M2 that we call the classes (α; β)-M2. Similarly, we characterize the class M3 through its set of minimal obstructions and present two families of minimal obstructions for any class Mi.
