5 papers
Testing H-freeness on sparse graphs, the case of bounded expansion
Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock +2
In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the gr…
On the Two Paths Theorem and the Two Disjoint Paths Problem
Samuel Humeau, Damien Pous
A tuple (s1,t1,s2,t2) of vertices in a simple undirected graph is 2-linked when there are two vertex-disjoint paths respectively from s1 to t1 and s2 to t2. A graph is 2-linked whe…
Making Graphs Irregular through Irregularising Walks
Julien Bensmail, Romain Bourneuf, Paul Colinot +2
The 1-2-3 Conjecture, introduced by KaroÅski, Åuczak, and Thomason in 2004, was recently solved by Keusch. This implies that, for any connected graph different from , we…
Correspondences between codensity and coupling-based liftings, a practical approach
Samuel Humeau, Daniela Petrisan, Jurriaan Rot
The Kantorovich distance is a widely used metric between probability distributions. The Kantorovich-Rubinstein duality states that it can be defined in two equivalent ways: as a su…
A finite presentation of graphs of treewidth at most three
Amina Doumane, Samuel Humeau, Damien Pous
We provide a finite equational presentation of graphs of treewidth at most three, solving an instanceof an open problem by Courcelle and Engelfriet. We use a syntax generalising se…