Índice cromático acíclico de grafos 1-planos
Autores: Yang, Wanshun; Wang, Yiqiao; Wang, Weifan; Liu, Juan; Finbow, Stephen; Wang, Ping
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Índice cromático acíclico de grafos 1-planos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
índice cromático acíclico
Grafo
Coloreable de arista propia
Grafo 1-planar
Grado máximo
Libre de triángulos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 24
Citaciones: Sin citaciones
El índice cromático acíclico de un grafo es el más pequeño para el cual es coloreable de manera adecuada utilizando colores. Un grafo 1-planar es un grafo que puede ser dibujado en un plano de manera que cada arista es cruzada por a lo sumo otra arista. En este artículo, demostramos que todo grafo 1-planar tiene , donde denota el grado máximo de . Esto refuerza un resultado que si es un grafo 1-planar libre de triángulos, entonces .
Descripción
El índice cromático acíclico de un grafo es el más pequeño para el cual es coloreable de manera adecuada utilizando colores. Un grafo 1-planar es un grafo que puede ser dibujado en un plano de manera que cada arista es cruzada por a lo sumo otra arista. En este artículo, demostramos que todo grafo 1-planar tiene , donde denota el grado máximo de . Esto refuerza un resultado que si es un grafo 1-planar libre de triángulos, entonces .