La decomposibilidad de grafos toroidales sin triángulos adyacentes o ciclos cortos
Autores: Lu, Huajing; Li, Fengwei
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
La decomposibilidad de grafos toroidales sin triángulos adyacentes o ciclos cortos
Categoría
Matemáticas
Subcategoría
Análisis matemático
Palabras clave
Grafo
Descomposición
Toroidal
Triángulos adyacentes
Ciclos
DP-3-coloreable
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
Un grafo tiene una -descomposición si hay un par tal que es un subgrafo de y es una orientación acíclica de , donde el grado máximo de es no más de y el máximo grado de salida de es no más de . Este documento demuestra que los grafos toroidales que no tienen triángulos adyacentes son -descomponibles, y para , los grafos toroidales sin - y -ciclos son -descomponibles. Como consecuencia de estos resultados, los grafos toroidales sin triángulos adyacentes son 1-defectuosos DP-4-colorables, y los grafos toroidales sin - y -ciclos son 1-defectuosos DP-3-colorables para .
Descripción
Un grafo tiene una -descomposición si hay un par tal que es un subgrafo de y es una orientación acíclica de , donde el grado máximo de es no más de y el máximo grado de salida de es no más de . Este documento demuestra que los grafos toroidales que no tienen triángulos adyacentes son -descomponibles, y para , los grafos toroidales sin - y -ciclos son -descomponibles. Como consecuencia de estos resultados, los grafos toroidales sin triángulos adyacentes son 1-defectuosos DP-4-colorables, y los grafos toroidales sin - y -ciclos son 1-defectuosos DP-3-colorables para .