3 citations · 3 across the 2 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
math.CO2020
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…
math.CO2020
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…
math.CO2020
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…