Comentarios sobre la conjetura de irregularidad local
Autores: Sedlar, Jelena; krekovski, Riste
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Comentarios sobre la conjetura de irregularidad local
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Localmente irregular
Grafo
Coloración de aristas
Coloreable
índice cromático
Conjetura
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
Un grafo localmente irregular es un grafo en el que los vértices finales de cada arista tienen grados distintos. Un coloreo irregular local de aristas de un grafo es cualquier coloreo de aristas tal que cada uno de los colores induce un subgrafo localmente irregular. Un grafo es coloreable si permite un coloreo irregular local de aristas. El índice cromático localmente irregular de un grafo coloreable , denotado por , es el menor número de colores utilizado por un coloreo irregular local de aristas de . La conjetura de irregularidad local afirma que todos los grafos, excepto los caminos de longitud impar, los ciclos de longitud impar y una cierta clase de cactus, son coloreables con tres colores. Dado que la conjetura es válida para grafos con un grado mínimo grande y todos los grafos no coloreables son cactus disjuntos por vértices, estudiamos grafos bastante dispersos. En este artículo, presentamos un grafo cactus que contradice esta conjetura, es decir, . Sin embargo, demostramos que la conjetura es válida para grafos unicíclicos y cactus con ciclos disjuntos por vértices.
Descripción
Un grafo localmente irregular es un grafo en el que los vértices finales de cada arista tienen grados distintos. Un coloreo irregular local de aristas de un grafo es cualquier coloreo de aristas tal que cada uno de los colores induce un subgrafo localmente irregular. Un grafo es coloreable si permite un coloreo irregular local de aristas. El índice cromático localmente irregular de un grafo coloreable , denotado por , es el menor número de colores utilizado por un coloreo irregular local de aristas de . La conjetura de irregularidad local afirma que todos los grafos, excepto los caminos de longitud impar, los ciclos de longitud impar y una cierta clase de cactus, son coloreables con tres colores. Dado que la conjetura es válida para grafos con un grado mínimo grande y todos los grafos no coloreables son cactus disjuntos por vértices, estudiamos grafos bastante dispersos. En este artículo, presentamos un grafo cactus que contradice esta conjetura, es decir, . Sin embargo, demostramos que la conjetura es válida para grafos unicíclicos y cactus con ciclos disjuntos por vértices.