en los grafos colorables en otoño
Autores: Wang, Shaojun; Wen, Fei; Wang, Guoxing; Li, Zepeng
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
en los grafos colorables en otoño
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Grafo
Caída
Colorear
Vértice
Grado mínimo
Plano
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
Una coloración de otoño de un grafo es una coloración propia tal que cada vértice tiene al menos un vecino en cada una de las otras clases de colores. Un grafo que tiene una coloración de otoño es equivalente a tener una partición del conjunto de vértices en conjuntos dominantes independientes. En este documento, primero demostramos que para cualquier grafo colorable de otoño con orden , el número de aristas de es al menos , donde y , y el límite es ajustado. Luego, obtenemos que si es -colorable () y el grado mínimo de es al menos , entonces es colorable de otoño y esta condición de grado mínimo es la mejor posible. Además, damos una prueba simple para un resultado NP-duro de determinar si un grafo es colorable de otoño, donde . Finalmente, mostramos que existe una familia infinita de grafos planares colorables de otoño para .
Descripción
Una coloración de otoño de un grafo es una coloración propia tal que cada vértice tiene al menos un vecino en cada una de las otras clases de colores. Un grafo que tiene una coloración de otoño es equivalente a tener una partición del conjunto de vértices en conjuntos dominantes independientes. En este documento, primero demostramos que para cualquier grafo colorable de otoño con orden , el número de aristas de es al menos , donde y , y el límite es ajustado. Luego, obtenemos que si es -colorable () y el grado mínimo de es al menos , entonces es colorable de otoño y esta condición de grado mínimo es la mejor posible. Además, damos una prueba simple para un resultado NP-duro de determinar si un grafo es colorable de otoño, donde . Finalmente, mostramos que existe una familia infinita de grafos planares colorables de otoño para .