The goal of local certification is to locally convince the vertices of a graph G that G satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view, they must decide whether G satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates.
In this talk, we study the local certification of geometric and topological graph classes. While it is known that in n-vertex graphs, planarity can be certified locally with certificates of size O(log n), we show that several closely related graph classes require certificates of linear size. This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain an almost linear lower bound on the size of the certificates, and an upper bound of O(n log n).

The H-coloring problems asks whether there is a graph homomorphism from a given graph G to a fixed template graph H. The complexity of H-coloring is well understood in the sense that there is a classification that tells us (even for digraphs), for which graphs H the problem is in P or NP-complete. Less is known for the so-called H-recoloring problem: given two homomorphisms from G to H, can one be transformed into the other step-by-step, changing the image of a single vertex of G at each step and keeping a homomorphism from G to H throughout? Similarly, H-mixing asks whether such a transformation exists for any two homomorphisms from G to H. We present a unified view of recent complexity results for H-recoloring and H-mixing and the topological tools that are used.

Given a set F of 2-edge-coloured graphs and a hereditary property of graphs P, we say that F expresses P if a graph G has the property P if and only if it admits a 2-edge-colouring not having any graph in F as an induced 2-edge-coloured subgraph. In this talk, we consider the following problems. Given a hereditary property of graphs, determine if is it possible to express it by a finite set of 2-edge-coloured graphs. Given a finite set of 2-edge-coloured graphs, find an useful characterization of the hereditary property it expresses. Given a finite set of 2-edge-coloured graphs, determine the complexity of recognizing the hereditary property it expresses.

The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of that vertex while preserving their degrees. Lovász (1974) and Mader (1978) showed the existence of this operation while preserving global and local connectivities respectively in graphs under mild conditions. In this talk, I will introduce a splitting-off operation in hypergraphs. Main results are that there exists a local connectivity preserving complete splitting-off in hypergraphs and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs. If time permits, I will illustrate the usefulness of our splitting-off operation in hypergraphs by showing two applications:
(1) constructive characterization of k-hyperedge-connected hypergraphs and
(2) alternate proof of an approximate min-max relation for max Steiner rooted-connected orientation of graphs and hypergraphs (due to Király and Lau (Journal of Combinatorial Theory, 2008)). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams' strong orientation theorem and uses tools developed for hypergraphs.

Based on joint work with Kristof Berczi, Tamas Kiraly, and Shubhang Kulkarni.