Partitioning planar graphs without specific cycles into a forest and a disjoint union of paths
Autores: Sittitrai, Pongpat; Nakprasit, Keaitsuda Maneeruk; Nakprasit, Kittikorn
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Partitioning planar graphs without specific cycles into a forest and a disjoint union of paths
Categoría
Matemáticas
Subcategoría
Análisis matemático
Palabras clave
Grafo
Planar
Caras
Bosque
Ciclos
Partición
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 19
Citaciones: Sin citaciones
En este documento, mostramos que si un grafo plano satisface las siguientes condiciones: (i) ninguno de sus 3-caras es adyacente a una -cara, y (ii) ninguno de sus 4-caras es adyacente a una -cara, entonces puede ser particionado en dos subconjuntos, cada uno induce un bosque, mientras que uno de los bosques tiene un grado máximo de a lo sumo. Este resultado implica que todo grafo plano (i) sin ciclos cordales - o (ii) sin ciclos de 4 ni de 6, también admite tal partición.
Descripción
En este documento, mostramos que si un grafo plano satisface las siguientes condiciones: (i) ninguno de sus 3-caras es adyacente a una -cara, y (ii) ninguno de sus 4-caras es adyacente a una -cara, entonces puede ser particionado en dos subconjuntos, cada uno induce un bosque, mientras que uno de los bosques tiene un grado máximo de a lo sumo. Este resultado implica que todo grafo plano (i) sin ciclos cordales - o (ii) sin ciclos de 4 ni de 6, también admite tal partición.