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 ...

jeu. 05 décembre 2024 -- Jonathan Narboni (LaBRI)

summary: The Borodin-Kostochka conjecture, a long-standing problem in graph theory, asserts that every graph \(G\) with maximum degree \(\Delta \geq 9\) satisfies \(\chi(G) \leq max \{\Delta - 1, \omega(G)\}\) where \(\chi(G)\) and \(\omega(G)\) are respectively the chromatic number and the clique number of \(G\). While the conjecture ...

jeu. 14 novembre 2024 -- Clément Rambaud (Université Côte d'Azur)

summary: For every positive integer k, we define the k-treedepth as the largest graph parameter td_k satisfying (i) td_k(∅)=0; (ii) td_k(G) <= 1+ td_k(G-u) for every graph G and every vertex u; and (iii) if G is a (

jeu. 24 octobre 2024 -- Djamel Amir (LISN, Galac)

summary: The topological properties of a set have a strong impact on its computability properties. A striking illustration of this idea is given by spheres, closed manifolds and finite graphs without endpoints : if a set X is homeomorphic to a sphere, a closed manifold or such a graph, then any ...