Coloración total de grafos planares maximales de mancuerna
Autores: Zhou, Yangyang; Zhao, Dongyang; Ma, Mingyuan; Xu, Jin
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Coloración total de grafos planares maximales de mancuerna
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Conjetura de coloración total
Gráficos planares máximos de mancuernas
Grado máximo
Gráficos planares máximos de I-mancuernas
8 coloreable
Algoritmo de tiempo lineal
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
La Conjetura de Coloración Total (TCC) afirma que todo grafo simple es totalmente -coloreable, donde denota el grado máximo de . En este documento, demostramos que TCC se cumple para grafos planares máximos de mancuerna. En particular, dividimos los grafos planares máximos de mancuerna en tres categorías según el grado máximo: , grafos planares máximos de mancuerna tipo I y grafos planares máximos de mancuerna tipo II. Damos la condición necesaria y suficiente para los grafos planares máximos de mancuerna tipo I, y demostramos que cualquier grafo planar máximo de mancuerna tipo I es totalmente 8-coloreable. Además, se propone un algoritmo de tiempo lineal para calcular una coloración total para cualquier grafo planar máximo de mancuerna tipo I.
Descripción
La Conjetura de Coloración Total (TCC) afirma que todo grafo simple es totalmente -coloreable, donde denota el grado máximo de . En este documento, demostramos que TCC se cumple para grafos planares máximos de mancuerna. En particular, dividimos los grafos planares máximos de mancuerna en tres categorías según el grado máximo: , grafos planares máximos de mancuerna tipo I y grafos planares máximos de mancuerna tipo II. Damos la condición necesaria y suficiente para los grafos planares máximos de mancuerna tipo I, y demostramos que cualquier grafo planar máximo de mancuerna tipo I es totalmente 8-coloreable. Además, se propone un algoritmo de tiempo lineal para calcular una coloración total para cualquier grafo planar máximo de mancuerna tipo I.