1 citations · 2 across the 15 of their papers we have counts for
11 papers · 1 filter
Linear clique-width and modular decomposition
Robert Brignall, Michal Opler, Vincent Vatter
A hereditary class of graphs has bounded clique-width if and only if its prime members do, but this lifting property fails for linear clique-width. We prove that a hereditary class…
Monadic Second-Order Logic of Permutations
Vít Jelínek, Michal Opler
Permutations can be viewed as pairs of linear orders, or more formally as models over a signature consisting of two binary relation symbols. This approach was adopted by Albert, Bo…
The Hierarchy of Hereditary Sorting Operators
Vít Jelínek, Michal Opler, Jakub Pekárek
We consider the following general model of a sorting procedure: we fix a hereditary permutation class , which corresponds to the operations that the procedure is allow…
Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters
Pavel Dvořák, Lukáš Folwarczný, Michal Opler +3
Functionality () is a graph parameter that generalizes graph degeneracy defined by Alecu et al. [JCTB, 2021]. They research the relation of functionality to many othe…
Griddings of permutations and hardness of pattern matching
Vít Jelínek, Michal Opler, Jakub Pekárek
We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations (the `text') and (the `pa…
Bears with Hats and Independence Polynomials
Václav Blažej, Pavel Dvořák, Michal Opler
Consider the following hat guessing game. A bear sits on each vertex of a graph , and a demon puts on each bear a hat colored by one of colors. Each bear sees only the hat c…
A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes
Vít Jelínek, Michal Opler, Jakub Pekárek
Permutation Pattern Matching (PPM) is the problem of deciding for a given pair of permutations P and T whether the pattern P is contained in the text T. Bose, Buss and Lubiw showed…
Two examples of Wilf-collapse
Michael Albert, Vít Jelínek, Michal Opler
Two permutation classes, the X-class and subpermutations of the increasing oscillation are shown to exhibit an exponential Wilf-collapse. This means that the number of distinct enu…
Wilf collapse in permutation classes
Michael Albert, Vít Jelínek, Michal Opler
For a hereditary permutation class , we say that two permutations and of are Wilf-equivalent in , if has the same numb…
Splittability and 1-amalgamability of permutation classes
Vít Jelínek, Michal Opler
A permutation class is splittable if it is contained in a merge of two of its proper subclasses, and it is 1-amalgamable if given two permutations and in , each with…
Major index distribution over permutation classes
Michal Opler
For a permutation the major index of is the sum of all indices such that . It is well known that the major index is equidistributed with the number of in…