20 citations · 75 across the 44 of their papers we have counts for
4 papers · 1 filter
Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs
Vadim Lozin, Barnaby Martin, Sukanya Pandey +4
For a fixed set of graphs, a graph is -subgraph-free if does not contain any as a (not necessarily induced) subgraph. A recently propo…
The complexity of L(p,q)-Edge-Labelling
Gaetan Berthe, Barnaby Martin, Daniel Paulusma +1
We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially class…
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
Jan Bok, Nikola Jedlickova, Barnaby Martin +3
A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injec…
The packing chromatic number of the infinite square lattice is between 13 and 15
Barnaby Martin, Franco Raimondi, Taolue Chen +1
Using a SAT-solver on top of a partial previously-known solution we improve the upper bound of the packing chromatic number of the infinite square lattice from 17 to 15. We discuss…