Vertex Cover is perhaps the most-studied problem in parameterized complexity that frequently serves as a testing ground for new concepts and techniques. In this talk, I will focus on a generalization of Vertex Cover called Component Order Connectivity (COC). Given a graph G, an integer k and a positive integer d, the task is to decide whether there is a vertex set S of size at most k such that each connected component of G – S has size at most d. If d = 1, then COC is the same as Vertex Cover. While almost all techniques to obtain polynomial kernels for Vertex Cover extend well to COC parameterized by k + d, the same cannot be said for structural parameters. Vertex Cover admits a polynomial kernel parameterized by the vertex deletion distance to treewidth 1 graphs, but not when parameterized by the deletion distance to treewidth 2 graphs. The picture changes when considering COC: It was recently shown that COC does not admit a polynomial kernel parameterized by the vertex deletion distance to treewidth 1 graphs with pathwidth 2, even if d ≥ 2 is a fixed constant. Complementing this, we show that COC does admit a polynomial kernel parameterized by the distance to graphs with pathwidth at most 1 (plus d). Hence, the deletion distance to pathwidth 1 vs. pathwidth 2 forms a similar line of tractability for COC as the distance to treewidth 1 vs. treewidth 2 does for Vertex Cover. In this talk, I will highlight the ideas and techniques that make this kernelization result possible.

Robertson and Seymour introduced branch-width as a connectivity invariant of graphs in their proof of the Wagner conjecture. Decompositions based on this invariant provide a natural framework for implementing dynamic-programming algorithms to solve graph optimization problems. We will discuss the computational issues involved in using branch-width as as a general tool in discrete optimization.

A graph $G$ is (list, DP) $k$-critical if the (list, DP) chromatic number is $k$ but for every proper subgraph $G’$ of $G$, the (list, DP) chromatic number of $G’$ is less than $k$. For $k\geq 4$, we show a bound on the minimum number of edges in a DP $k$-critical graph, and our bound is the first bound that is asymptotically better than the corresponding bound for proper $k$-critical graphs by Gallai from 1963. Our result also improves the best bound on the list chromatic number. This is joint work with Bradshaw, Kostochka, and Xu.

Given a $k$-uniform hypergraph $H$, the Ramsey number $R(H;q)$ is the smallest integer $N$ such that any $q$-coloring of the edges of the complete $k$-uniform hypergraph on $N$ vertices contains a monochromatic copy of $H$. When $H$ is a complete hypergraph, a classical argument of Erdős, Hajnal, and Rado reduces the general problem to the case of uniformity $k = 3$. In this talk, we will survey constructions that lift Ramsey numbers to higher uniformities and discuss recent progress on quantitative bounds for $R(H;q)$ for certain families of hypergraphs. This is joint work with Ayush Basu, Dániel Dobák, Pavel Pudlák, and Vojtěch Rödl.

Nowhere-zero flows of unsigned graphs were introduced by Tutte in 1954 as a dual problem to vertex-coloring of (unsigned) planar graphs. The definition of nowhere-zero flows on signed graphs naturally comes from the study of embeddings of graphs in non-orientable surfaces, where nowhere-zero flows emerge as the dual notion to local tensions.  Nowhere-zero flows in signed graphs were introduced by Edmonds and Johnson in 1970 for expressing algorithms on matchings, but systematically studied first by Bouchet in 1983. Bouchet also stated a conjecture which occupies a central place in the area of signed graphs: Every flow-admissible signed graph admits a nowhere-zero 6-flow.  There is a significant difference in the flows of signed graphs and unsigned graphs. In this talk I will talk about the progress on the development of the flow theory of signed graphs.

We prove that for all positive integers $k$ and $d$, the class of $K_{1,d}$-free graphs not containing the $k$-ladder or the $k$-wheel as an induced minor has a bounded tree-independence number. Our proof uses a generalization of the concept of brambles to tree-independence number. This is based on joint work with Claire Hilaire, Martin Milanič, and Sebastian Wiederrecht.

We will discuss two symmetry breaking parameters: distinguishing number and fixing number. Despite being introduced independently, they share meaningful connections. In particular, we show that if a tree is 2-distinguishable with order at least 3, it suffices to fix at most 4/11 of the vertices and if a tree is $d$-distinguishable, $d \geq 3$, it suffices to fix at most $\frac{d-1}{d+1}$ of the vertices. We also characterize the $d$-distinguishable trees with radius $r$, for any $d \geq 2$ and $r \geq 1$. This is joint work with Calum Buchanan, Peter Dankleman, Isabel Harris, Paul Horn, and Emily Rivett-Carnac.

Lehel's conjecture states that every 2-edge-colouring of the complete graph $K_n$ admits a partition of its vertices into two monochromatic cycles. This was proven for sufficiently large n by Luczak, Rödl, and Szemerédi (1998), extended by Allen (2008), and fully resolved by Bessy and Thomassé in 2010. We consider a rainbow version of Lehel’s conjecture for properly edge-coloured complete graphs. We prove that for any properly edge-coloured $K_n$ with sufficiently large n, there exists a partition of the vertex set into two rainbow cycles, each containing no two edges of the same colour. This is joint work with Pedro Araújo, Xiaochuan Liu, Taísa Martins, Walner Mendonça, Luiz Moreira, and Vinicius Fernandes dos Santos.