Separating 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 path separation. We will go through a sketch of the proof and explain the importance of this result in the grand scheme of separating systems.

Posted on Oct 17, 2024 in Seminario de Grafos, Seminars