3 papers
math.CO2026
Transducing Linear Decompositions of Tournaments
Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté
BojaÅczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We…
cs.DM2025
Weakly-sparse and strongly flip-flat classes of graphs are uniformly almost-wide
Fatemeh Ghasemi, Julien Grange, Mamadou Moustapha Kanté +1
In this work we take a step towards characterising strongly flip-flat classes of graphs. Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting o…
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…