ven. 21 février 2025 -- Quentin Chuet (LISN, GALaC)

summary: Given a graph \(G\) of maximum degree \(\Delta\), the proper colouring problem asks for the minimum number of colours that can be assigned to the vertices of \(G\) such that no pair of adjacent vertices are given the same colour; it is easy to show that at most \(\Delta ...

ven. 14 février 2025 -- Pacôme Perrotin (LISN, Galac)

summary: Plane-walking automata were introduced by Salo & Törma to recognise languages of two-dimensional infinite words (subshifts), the counterpart of 4-way finite automata for two-dimensional finite words. We extend the model to allow for nondeterminism and alternation of quantifiers. We prove that the recognised subshifts form a strict subclass of sofic ...

jeu. 23 janvier 2025 -- Hugo Jacob (LaBRI)

summary: Tree-partitions are graph decompositions that correspond to mapping vertices to nodes of a tree in such a way that adjacent vertices in the graph are either mapped to adjacent nodes of the tree or to the same node. The width of a tree-partition is the maximum number of vertices ...

jeu. 12 décembre 2024 -- Loïc Le-Mogne (LaBRI)

summary: A flow graph \(G\) is an acyclic oriented graph with \(V(G) = [n]\), \(E(G)\) a multi-set of edges where each edge \((i,j)\) satisfies \(i<j\), and such that \(G\) has a unique source \(s=1\) and sink \(t=n\). On such a graph, a route is simply ...