Univerza na Primorskem
Fakulteta za matematiko, naravoslovje in informacijske tehnologije
Datum / Date: 12.10.26
Čas / Time: 15:00-16:00
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Nicolas Trotignon (CNRS, LIP, ENS de Lyon)
Naslov / Title: Pathographs and some undecidability results
Povzetek / Abstract:
We define pathographs, that is a generalization of graphs. Pathographs have vertices and edges, as graphs, but they also have «ur-path», that are special edges (that we will later subdivide). There are also spokes, that are adjacencies between vertices and ur-paths, and rungs, that are adjacencies between ur-paths. A realization of a pathograph G is any graph G’ obtained from G be replacing each ur-path by a path of length at least 2. Furthermore, for each spoke v-p there must be at least one edge between v and the path P arising from the ur-path p, and for each rung pq, there must be at least one edge between the paths P, Q arising from p and q respectively. There are no other vertices or edges.
We consider the problem whose instance is a pathgraph G and a finite set of graphs F. The question is whether there exists a realization of G that contains no graph from F as an induced subgraph. We prove that this problem is undecidable (by reducing the Wang tiles problem to it). This result has several motivations. Pathographs are flexible enough to encode several graph containment problems. Some of them seems easy though it not known whether an algorithm exists for them, and our result show that this is not trivial. Also, many proofs in structural graph theory relies on a fact that some pathograph cannot be realized without introducing a forbidden induced subgraphs, so our result show that automatic provers for such lemmas do not exists in general.
This is a joint work with Daniel Carter.