DP-4-Colorabilidad en grafos planares excluyendo 7-ciclos adyacentes a 4- o 5-ciclos
Autores: Yang, Fan; Li, Xiangwen; Huang, Ziwen
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
DP-4-Colorabilidad en grafos planares excluyendo 7-ciclos adyacentes a 4- o 5-ciclos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Resolver
Conjetura de Borodin
Coloreado dp
Grafo planar
7-ciclos
Mariposas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 19
Citaciones: Sin citaciones
Para resolver la Conjetura de Borodin, se introdujo la coloración DP en 2017 para ampliar el concepto de coloración de listas. En trabajos anteriores, se demostró que todo grafo planar sin ciclos de 7 y mariposas es DP-4-cromático. Y cualquier grafo planar que no tenga un ciclo de 5 adyacente a un ciclo de 6 es DP-4-cromático. La investigación existente se centra principalmente en los ciclos adyacentes prohibidos que garantizan la DP-4-cromabilidad para el grafo planar. En este documento, demostramos que cualquier grafo planar que excluya ciclos de 7 adyacentes a ciclos k (para cada k), y que no presente un Near-bow-tie como subgrafo inducido, es DP-4-cromático. Este resultado amplía los hallazgos de los trabajos anteriores mencionados anteriormente.
Descripción
Para resolver la Conjetura de Borodin, se introdujo la coloración DP en 2017 para ampliar el concepto de coloración de listas. En trabajos anteriores, se demostró que todo grafo planar sin ciclos de 7 y mariposas es DP-4-cromático. Y cualquier grafo planar que no tenga un ciclo de 5 adyacente a un ciclo de 6 es DP-4-cromático. La investigación existente se centra principalmente en los ciclos adyacentes prohibidos que garantizan la DP-4-cromabilidad para el grafo planar. En este documento, demostramos que cualquier grafo planar que excluya ciclos de 7 adyacentes a ciclos k (para cada k), y que no presente un Near-bow-tie como subgrafo inducido, es DP-4-cromático. Este resultado amplía los hallazgos de los trabajos anteriores mencionados anteriormente.