Una condición suficiente para que los grafos planares de grado máximo 6 sean totalmente 7-coloreables.
Autores: Zhu, Enqiang; Rao, Yongsheng
Idioma: Inglés
Editor: Hindawi
Año: 2020
Acceso abierto
Artículo científico
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Grafo
Coloración total
Conjetura
Plano
Grado máximo
Ciclos de 4 nodos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 27
Citaciones: Sin citaciones
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
Descripción
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