logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro