13 citations · 77 across the 56 of their papers we have counts for
10 papers · 1 filter
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…
Induced matching treewidth and tree-independence number, revisited
Noga Alon, Martin Milanič, Paweł Rzążewski
We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with…
Hitting all longest paths in -free graphs and -graphs
Paloma T. de Lima, Amir Nikabadi, Paweł Rzążewski
The \textit{longest path transversal number} of a connected graph , denoted by , is the minimum size of a set of vertices of that intersects all longest paths in …
List coloring ordered graphs with forbidden induced subgraphs
Marta Piecyk, Paweł Rzążewski
In the List -Coloring problem we are given a graph whose every vertex is equipped with a list, which is a subset of . We need to decide if admits a proper co…