Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / El k-coloreo de vértices de un grafo es un ya conocido problema NP-completo, debido a esto, los esfuerzos se han concentrado en estudiar el problema restringido a ciertas clases de grafos, para intentar resolverlo en tiempo polinomial. Dentro de las clases de grafos más estudiada, están los grafos H-free, que son los grafos que no poseen un grafo isomorfo a H como subgrafo inducido. En el presente trabajo se investigó el problema de 3-coloreo en las clases de grafos (P_{2d+3},C_{≤ 2d-1})-free (donde C_{≤2d−1} = {C_{2k+1} ∣ k ∈ N y k ≤ d}), para d ≥ 3, obteniendo los siguientes resultados: Para el caso particular d = 3, se puede decidir si un grafo G de la clase ( P_9, C_5, C_3)-free posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4). Para todo d ≥ 3, se puede decidir si un grafo G de la clase (P_{2d+3},C_{≤ 2d-1}, C_8)-free posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4). Para todo d ≥ 3, se puede decidir si un grafo G de la clase ( P_{2d+3}, C_{≤2d−1})-free, que tiene un ciclo C de largo 2d + 3 como subgrafo inducido, posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4). / CMM - Conicyt PIA AFB170001

This thesis consists of three parts devoted to graph labeling, hereditary graph classes, and parameterized complexity. Packing coloring, originally Broadcasting Chromatic number, assigns natural numbers to vertices such that vertices with the same label are in distance at least the value of the label. This problem is motivated by the assignment of frequencies to the transmitters. We improve hardness on chordal graphs. We proof that packing coloring on chordal graphs with diameter 3 is very hard to approximate. Moreover, we discuss several positive results on interval graphs and on related structural graph parameters. Hereditary graph classes are preserved under vertex deletion. We study graphs that do not contain an induced subgraph H. We prove that 3-coloring is polynomial-time solvable for (P3 + P4)-free and (P2 + P5)-free graphs and thus we have solved the last open cases for the problem on H-free graphs where H has up to 7 vertices. Fair problems are a modification of graph deletion problems, where, instead of minimizing the size of the solution, the aim is to minimize the maximum number of neighbors in the deleted set. We show that those problems can be solved in FPT time for an MSO1 formula parameterized by the size of the formula and the twin cover of the graph. Moreover, we define a basic...