logo móvil
Contáctanos

en los grafos colorables en otoño

Autores: Wang, Shaojun; Wen, Fei; Wang, Guoxing; Li, Zepeng

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

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


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 .

Otros recursos que podrían interesarte

Temas Virtualpro