Tesis Ingeniería Civil Matemática
URI permanente para esta colección
Examinar
Examinando Tesis Ingeniería Civil Matemática por Materia "COMBINATORIA"
Mostrando 1 - 2 de 2
Resultados por página
Opciones de ordenación
Ítem Estudio de extensiones de coloreo impar en grafos planares(Universidad de Valparaíso, 2026-01-29) Barahona Díaz, Yazmín Victoria; Jiménez Ramírez, Andrea Patricia; Echeverría González, Henry FernandoEste trabajo se enmarca en la teoría de grafos, específicamente en el estudio de variantes del coloreo impar en grafos planares. Motivado por aplicaciones en asignación de frecuencias y por recientes desarrollos teóricos, se analizan dos extensiones del coloreo impar: la coloración impar casi fuerte, introducida en esta investigación, y la coloración 2-impar, propuesta previamente en la literatura. Ambas nociones imponen restricciones de paridad en las ocurrencias de colores dentro del vecindario de cada vértice. El objetivo principal es estudiar el comportamiento de los números cromáticos asociados a estas coloraciones en distintas subclases de grafos planares. En primer lugar, se establecen cotas superiores ajustadas para árboles, grafos unicíclicos, ruedas y escaleras de Möbius, mostrando que estas estructuras permiten una caracterización precisa de los nuevos parámetros cromáticos. En particular, se evidencia que las coloraciones impar casi fuerte y 2-impar no son comparables en general, aunque coinciden en ciertas clases específicas. El foco central del trabajo se sitúa en los grafos outerplanares maximales. Se demuestra que, en esta clase, los números cromáticos impar casi fuerte y 2-impar coinciden, y que ambos están acotados superiormente por 6. La demostración utiliza una construcción recursiva de estos grafos junto con técnicas de permutación de colores y el análisis de testigos, que permiten extender coloraciones manteniendo las propiedades de paridad requeridas. Además, para la subclase de grafos outerplanares maximales sin “triángulos internos”, se prueba que la cota se reduce a 5 y que esta es óptima. Finalmente, se exploran clases más amplias de grafos planares, incluyendo grafos outerplanares no maximales y triangulaciones tipo stack (3-árboles planares). En estos casos, se obtienen nuevas cotas superiores, destacando que 7 colores son suficientes para grafos outerplanares generales y que 10 colores bastan para la coloración 2-impar en triangulaciones stack. En conjunto, el trabajo aporta nuevas definiciones, cotas mejoradas y herramientas metodológicas que contribuyen al entendimiento de las coloraciones impares en grafos planares y abren nuevas líneas de investigación en el área.Ítem Inmersiones en grafos con número de independencia dos(Universidad de Valparaíso, 2026) Bermúdez Bustos, Antonia; Quiroz Brito, DanielPara la teoría de grafos, uno de los mayores problemas consiste en entender la relación entre la estructura de un grafo y su número cromático. El buscar establecer esta relación ha dado origen a una gran cantidad de conjeturas y resultados relacionados con la coloración de grafos, siendo uno de los resultados más importantes el Teorema de los Cuatro Colores, el cual establece que todo grafo planar puede ser coloreado con a lo más cuatro colores. Como veremos, este teorema derivó en el desarrollo de una gran variedad de problemas relacionados con la existencia de determinadas subestructuras en grafos con número cromático alto. El número de clique de un grafo G , denotado por ω(G), corresponde al tamaño del mayor subgrafo completo en un grafo G. Dado que para un grafo completo de n vértices su número cromático es χ(G) = n, entonces, para cualquier grafo G, se tiene que ω(G) ≤ χ(G), ya que un grafo completo debe recibir colores distintos en cada vértice; sin embargo, la desigualdad contraria no es cierta. En este sentido, el Teorema de Mycielski nos dice que hay grafos sin un completo en 3 vértices y número cromático arbitrariamente alto. Esto deja como consecuencia que un número cromático elevado no garantiza que el grafo tenga una subestructura completa como subgrafo. No obstante, se esperaría que un grafo con número cromático alto contenga una subestructura completa en un sentido más débil, lo que ha llevado al estudio de diversas formas de contención de grafos, como las subdivisiones, menores e inmersiones. Una de las conjeturas más importantes que relaciona el número cromático y la contención de subestructuras completas es la Conjetura de Hadwiger, la cual dice que todo grafo G con número cromático χ(G) contiene a Kχ(G) como menor. Aunque esta afirmación sigue abierta, la conjetura ha llevado a la elaboración de varias variantes donde se reemplaza la noción de menor por otras formas de contención. En el presente trabajo se abordarán conjeturas análogas a la Conjetura de Hadwiger para inmersiones completas. En particular, se estudiará la Conjetura de Lescure y Meyniel (1989), la que establece que todo grafo G contiene una inmersión de un grafo completo Kχ(G). Esto da paso a la Conjetura de Vergara (2017), que propone que todo grafo G con n vértices y número de independencia ∼2 contiene una inmersión de K⌈n/2⌉ Nuestro primer resultado restringe la familia de grafos que pueden formar un contraejemplo mínimo a la Conjetura de Vergara. Así, se demuestra que todo contraejemplo mínimo a la Conjetura de Vergara debe contener como subgrafo inducido al ciclo C5 añadiendo un vértice externo adyacente a exactamente tres vértices del ciclo. Luego, se demuestra que todo grafo con número de independencia dos contiene a Kχ(G) como menor o como inmersión. Finalmente, se verifica la Conjetura de Vergara para todo grafo con a lo más diez vértices; es decir, se demuestra que si G tiene n ≤ 10 vértices y número de independencia 2, entonces G contiene una inmersión K⌈n/2⌉