4 papers
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…
A note on connected greedy edge colouring
Marthe Bonamy, Carla Groenland, Carole Muller +3
Following a given ordering of the edges of a graph , the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus i…
Characterization of 4-critical triangle-free toroidal graphs
Zdeněk Dvořák, Jakub Pekárek
We give an exact characterization of 3-colorability of triangle-free graphs drawn in the torus, in the form of 186 "templates" (graphs with certain faces filled by arbitrary quadra…
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…