Noticias en español
Complexity of k-coloring (subdivided claw)-free graphs with bounded diameter.
Abstract: During the last decades, there has been a lot of research on the computational complexity of k-coloring in H- free graphs when H is a linear forest. It is known that k-coloring $K_{1,3}$ (claw) free graphs is NP-complete for $k\geq 3$.In this talk, we will study the techniques used by Barnaby Martin, Daniël Paulusma and Siani Smith in 2021 to generalize this result for $K^{r}_{1,3}$ (subdivided claw) free graphs with bounded diameter.
Read MoreDistributive absorption: an example of use.
Abstract: The absorption method is a versatile technique for extending approximate results into exact ones. A new implementation of this technique, called distributive absorption, was introduced by Montgomery in 2019. In this talk, we present how the distributive absorption was used by Montgomery, Pokrovskiy and Sudakov to extend an approximate result for Ringel’s conjecture into an exact one.
Read MoreRecent progress on tree packings.
Abstract:We say that a graph H decomposes a graph G if the edges of G can be partitioned into edge-disjoint copies of H. In 1976, Ringel conjectured that any tree of order n+1 decomposes the complete graph on 2n+1 vertices. Recently Montgomery, Pokrovskiy and Sudakov presented a proof of this conjecture for large n. In this talk, we will study the techniques used by Montgomery, Pokrovskiy and Sudakov to prove Ringel’s conjecture.
Read MoreEl grupo de automorfismos de los grafos de fichas de los bipartitos completos.
Abstract: Sea $G$ una gráfica simple de $n$ vértices y $k$ un entero tal que $1\leq k\leq n-1$. El grafo de $k$-fichas, $F_k(G)$, de $G$ es el grafo cuyos vértices son los $k$-conjuntos de vértices de $G$, y donde dos de estos $k$-conjuntos son adyacentes si su diferencia simétrica es una arista de $G$. En esta plática hablaremos sobre la relación que existe entre los grupos de automorfismos de $G$ y de $F_k(G)$. Además, daremos un bosquejo de la prueba para determinar el grupo de automorfismos de $F_k(K_{m,n})$, donde $K_{m,n}$ denota al grafo bipartito completo. En esta familia de grafos...
Read MoreEmpaquetamiento óptimo de árboles de grado máximo acotado.
Abstract: En 1976, Gyárfás y Lehel conjeturaron que si T_1,…, T_n es una secuencia de árboles tal que T_i tiene i vértices, entonces el grafo completo en n vértices K_n tiene una descomposición en T_1,…, T_n. Recientemente, Joos, Kim, Kühn y Osthus [1] probaron esta conjetura para árboles de grado máximo acotado. En este seminario vamos a estudiar las técnicas utilizadas en la demostración de este resultado. En especial, veremos una aplicación del método de absorción iterativo. [1] Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus, Optimal packings of bounded degree trees. J....
Read MoreStructural properties in hypercubes.
Abstract: In this talk we review some structural questions on subgraphs of the hypercube of dimension n. We present a simpler proof of Huang’s 2019 result that any subgraph of $H_n$ on more than half the number of vertices has a vertex of degree at least $\sqrt{n}$. We present some strengthening of the result, and we observe a connection to an older question of Erdos who asked: how many edges of $H_n$ one should take to guarantee existence of a 4-cycle.
Read More