Monocromático grafico descomposiciones inspiradas por la teoría anti-Ramsey y restricciones de paridad
Autores: Caro, Yair; Tuza, Zsolt
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Monocromático grafico descomposiciones inspiradas por la teoría anti-Ramsey y restricciones de paridad
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Coloración de aristas
Teoría anti-Ramsey
Coloraciones libres de conflictos
Coloración arcoíris
Coloraciones impares
Grafos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 35
Citaciones: Sin citaciones
Abrimos aquí muchas nuevas líneas de investigación en Teoría Anti-Ramsey, considerando problemas de coloreo de aristas inspirados en el coloreo arcoíris y además en coloreos impares y coloreos libres de conflictos. Sea un grafo y una familia dada de grafos. Para cada entero , sea la menor entero tal que cualquier coloreo de aristas de con al menos colores obliga a una copia de en la cual cada clase de color induce un miembro de . Observar que en problemas anti-Ramsey, cada clase de color es una sola arista, es decir, . Entre los muchos resultados presentados en este documento, mencionamos lo siguiente. (1) Para cada grafo , existe una constante tal que en cualquier coloreo de aristas de con al menos colores hay una copia de en la cual cada vértice incide en una arista cuyo color aparece solo una vez entre todas las aristas incidentes con . (2) En marcado contraste con el resultado anterior, demostramos que si es la clase de todos los grafos impares (con vértices de grados impares únicamente) entonces , lo cual es cuadrático para . (3) Determinamos exactamente para grafos pequeños cuándo pertenece a varias familias que representan varias restricciones de coloreo par/impar.
Descripción
Abrimos aquí muchas nuevas líneas de investigación en Teoría Anti-Ramsey, considerando problemas de coloreo de aristas inspirados en el coloreo arcoíris y además en coloreos impares y coloreos libres de conflictos. Sea un grafo y una familia dada de grafos. Para cada entero , sea la menor entero tal que cualquier coloreo de aristas de con al menos colores obliga a una copia de en la cual cada clase de color induce un miembro de . Observar que en problemas anti-Ramsey, cada clase de color es una sola arista, es decir, . Entre los muchos resultados presentados en este documento, mencionamos lo siguiente. (1) Para cada grafo , existe una constante tal que en cualquier coloreo de aristas de con al menos colores hay una copia de en la cual cada vértice incide en una arista cuyo color aparece solo una vez entre todas las aristas incidentes con . (2) En marcado contraste con el resultado anterior, demostramos que si es la clase de todos los grafos impares (con vértices de grados impares únicamente) entonces , lo cual es cuadrático para . (3) Determinamos exactamente para grafos pequeños cuándo pertenece a varias familias que representan varias restricciones de coloreo par/impar.