Sebastian Siebertz, Rank-width meets stability

Zoom ID: 869 4632 6610 (ibsdimag)

Forbidden graph characterizations provide a convenient way of specifying graph classes, which often exhibit a rich combinatorial and algorithmic theory. A prime example in graph theory are classes of bounded tree-width, which are characterized as those classes that exclude some planar graph as a minor. Similarly, in model theory, classes of structures are characterized by

Sebastian Siebertz, Transducing paths in graph classes with unbounded shrubdepth

Zoom ID: 869 4632 6610 (ibsdimag)

Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class C can be FO-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from C one cannot FO-transduce the class of all paths. This establishes

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.