logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro