3 papers
cs.DS2025
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…
cs.DM2025
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 c…
cs.DS2025
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…