Noticias en español
Rainbow path separation systems (RPSS)
Abstract: A family of paths P in a graph G is (k,t)-rainbow separating if it can be coloured with k colours such that for every t-tuple of edges e_1, …, e_t there exist t paths P_1, …, P_t of distinct colours such that P_i contains the edge e_i and does not contain any other edge of the t-tuple. Much work has been done on (∞,2)-RPSS, also known as strong path separation systems. In this talk I will present some optimal results on (2,2)-RPSS, together with a more general treatise on (k,2)-RPSS for all values of k.
Read MoreMetric properties of locally connected graphs.
Abstract: A set of n points in the plane which are not all collinear defines at least n distinct lines. In 2008, Chen and Chvátal conjectured that this property holds for all finite metric spaces. This conjecture is still open, even for metric spaces induced by graphs. In this talk, we show that locally connected graphs satisfy this property and an even stronger one.
Read MoreTurán problem for edge-ordered graphs.
Abstract: The Turán-type extremal problem asks how many edges an n-vertex simple graph can have if it does not contain a subgraph isomorphic to a forbidden graph. The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner, Methuku, Nagy, Pálvölgyi, Tardos, and Vizer in 2020. A simple graph is called edge-ordered if its edges are linearly ordered. Gerbner et al. defined a parameter called order chromatic number for edge-ordered graphs and proved an Erdős-Stone-Simonovits-type theorem for edge ordered graphs that determines the Turán number of an...
Read MorePowers of Hamilton cycles in directed and oriented graphs.
Abstract: The P\’osa–Seymour conjecture determines the minimum degree threshold for forcing the $k$th power of a Hamilton cycle in a graph. After numerous partial results, Koml\’os, S\’ark\”ozy and Szemer\’edi proved the conjecture for sufficiently large graphs. We focus on the analogous problem for digraphs and for oriented graphs. For digraphs, we asymptotically determine the minimum total degree threshold for forcing the square of a Hamilton cycle. We also give a conjecture on the corresponding threshold for $k$th powers of a Hamilton cycle more...
Read MoreSeparating the edges of a graph with linearly many subdivisions of K_4.
Abstract: Let G be a graph. As we recall from Ana’s talk, a set S of subgraphs of G is (strongly) separating if for every ordered pair of edges (e,f) in E(G)^2 there exists a subgraph H in S that contains e but not f. Although we traditionally view S as a set of paths, other kinds of separating sets have also been considered. Recently, Botler and Naia proved that every graph can be separated by a set S of subdivisions of K_4 (and lone edges, which are necessary for covering bridges), such that the size of S is a linear function of |V(G)|. This mirrors the corresponding theorem about...
Read MoreDrawing Planar Graphs Badly.
Abstract: We study how far one can deviate from optimal behavior when drawing a planar graph on a plane. For a planar graph $G$, we say that a plane subgraph $H\subseteq G$ is a \textit{plane-saturated subgraph} if adding any edge (possibly with a new vertex) to $H$ would either violate planarity or make the resulting graph no longer a subgraph of $G$. For a planar graph $G$, we define the \textit{plane-saturation ratio}, $\psr(G)$, as the minimum value of $\frac{e(H)}{e(G)}$ for a plane-saturated subgraph $H\subseteq G$ and investigate how small $\psr(G)$ can be. While there exist planar...
Read More