3 papers
cs.LO2026
Monadic dependence from reducts, and applications to twin-width of oriented graphs
Hector Buffière, Yuquan Lin, Patrice Ossona de Mendez
We study monadic dependence of binary relational structures including at least one antisymmetric relation. Our cornerstone result gives sufficient conditions for proving that a str…
math.CO2024
Colouring negative exact-distance graphs of signed graphs
Reza Naserasr, Patrice Ossona de Mendez, Daniel A. Quiroz +2
The -th exact-distance graph, of a graph has as its vertex set, and as an edge if and only if the distance between and is (exactly) in . We consid…
math.CO2024
Shallow vertex minors, stability, and dependence
H. Buffière, E. Kim, P. Ossona de Mendez
Stability and dependence are model-theoretic notions that have recently proved highly effective in the study of structural and algorithmic properties of hereditary graph classes, a…