4 papers
Characterizations of monadically dependent tree-ordered weakly sparse structures
Hector Buffière, Yuquan Lin, Jaroslav NeÅ¡etÅil +2
A class of structures is monadically dependent if one cannot interpret all graphs in colored expansions from the class using a fixed first-order formula. A tree-ordered -struct…
On Computational Aspects of Cores of Ordered Graphs
Michal ÄertÃk, Andreas Emil Feldmann, Jaroslav NeÅ¡etÅil +1
An ordered graph is a graph enhanced with a linear order on the vertex set. An ordered graph is a core if it does not have an order-preserving homomorphism to a proper subgraph. We…
On Computational Aspects of Ordered Matching Problems
Michal ÄertÃk, Andreas Emil Feldmann, Jaroslav NeÅ¡etÅil +1
Ordered matchings, defined as graphs with linearly ordered vertices, where each vertex is connected to exactly one edge, play a crucial role in the area of ordered graphs and their…
Complexity Aspects of Homomorphisms of Ordered Graphs
Michal ÄertÃk, Andreas Emil Feldmann, Jaroslav NeÅ¡etÅil +1
We examine ordered graphs, defined as graphs with linearly ordered vertices, from the perspective of homomorphisms (and colorings) and their complexities. We demonstrate the corres…