Resumen

Una coloración total de un grafo es una asignación de colores a sus vértices y aristas de manera que ningún par de elementos adyacentes o incidentes reciba el mismo color. La conjetura de coloración total (TCC) establece que todo grafo simple tiene una coloración total, donde es el grado máximo de . Esta conjetura ha sido confirmada para grafos planares con grado máximo al menos 7 o como máximo 5, es decir, el único caso abierto de TCC es el de grado máximo 6. Se sabe que todo grafo planar de o con algunas restricciones tiene una coloración total. En particular, en (Shen y Wang, 2009), los autores demostraron que todo grafo planar con grado máximo 6 y sin ciclos de 4 vértices tiene una coloración total de 7 colores. En este documento, mejoramos este resultado al mostrar que todo grafo planar libre de diamantes y casas, con grado máximo 6, es totalmente 7-colorable si cada vértice de 6 no está incidente con dos ciclos de cuatro vértices ady

• Materias:Virus informático Entropía del gráfico Modelo epidémico Modelo de optimización Modelos conceptuales
• Subjects:Computer virus Entropy of the graph Epidemic model Optimization model Conceptual models
• Palabras claves:Grafo; Coloración total; Conjetura; Plano; Grado máximo; Ciclos de 4 nodos
• Keywords:Graph; Total coloring; Conjecture; Planar; Maximum degree; 4-cycles