Inmersiones en grafos con número de independencia dos

Abstract

Para 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⌉