118 citations · 187 across the 14 of their papers we have counts for
4 papers · 1 filter
Two dichotomies for model-checking in multi-layer structures
Jessica Enright, Kitty Meeks, Jessica Ryan
Multi-layer graphs can capture qualitatively different types of connection between entities, and networks of this kind are prevalent in biological and social systems: for example,…
Equivalence of the filament and overlap graphs of subtrees of limited trees
Jessica Enright, Lorna Stewart
The overlap graphs of subtrees of a tree are equivalent to subtree filament graphs, the overlap graphs of subtrees of a star are cocomparability graphs, and the overlap graphs of s…
On List Colouring and List Homomorphism of Permutation and Interval Graphs
Jessica Enright, Lorna Stewart, Gabor Tardos
List colouring is an NP-complete decision problem even if the total number of colours is three. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for…
3-List Colouring Permutation Graphs
Jessica Enright, Lorna Stewart
3-list colouring is an NP-complete decision problem. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving 3-list colouring on permutation gra…