Condiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados (segunda parte).

 Abstract: Diremos que un grafo $G$ apunta a un grafo $H$ si es que en cada $2$-arista-coloreo de $G$ existe una copia monocromática de $H$. Schelp tenía la idea de que si el grafo completo $K_n$ apunta un grafo pequeño $H$, entonces cada subgrafo denso de $K_n$ también apunta a H.En este seminario, veremos un resultado demostrado por Balogh, Kostochka, Lavrov y Liu en 2021 ( https://arxiv.org/pdf/1906.02854.pdf ) que indica que “para todo $n$ suficientemente grande, si $n = 3t + r$ donde $r\in\{0,1,2\} y $G$ es un grafo en $n$ vértices con $\delta(G) \geq (3n-1)/4$,entonces para todo $2$-arista coloreo de $G$, o bien hay ciclos de cadalargo en $\{3,4,5,…,2t+2\}$ de un mismo color o bien hay ciclos de cada largo par en $\{4, 6, 8, …, 2t + 2\}$ del mismo color”. Este resultadoresuelve algunas conjeturas planteadas por Schelp, Benevides, {\L}uczak,Scott, Skokan y White.

Posted on Jun 12, 2023 in Seminario de Grafos, Seminars