Jake Horsfield

activity

20202022

most citedBounding the Mim-Width of Hereditary Graph Classes

12 citations · 26 across the 4 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2020★ 10 cited

List $k$ -Colouring $P_{t}$ -Free Graphs: a Mim-width Perspective

Nick Brettell, Jake Horsfield, Andrea Munaro +1

A colouring of a graph $G = (V, E)$ is a mapping $c : V \to {1, 2, \dots}$ such that $c (u) \neq = c (v)$ for every two adjacent vertices $u$ and $v$ of $G$ . The {\sc List $k$ -Colourin…

cs.DS2020

Colouring $(s P_{1} + P_{5})$ -Free Graphs: a Mim-Width Perspective

Nick Brettell, Jake Horsfield, Daniel Paulusma

We prove that the class of $(K_{t}, s P_{1} + P_{5})$ -free graphs has bounded mim-width for every $s \geq 0$ and $t \geq 1$ , and that there is a polynomial-time algorithm that, given a graph i…

cs.DS2020★ 12 cited

Bounding the Mim-Width of Hereditary Graph Classes

Nick Brettell, Jake Horsfield, Andrea Munaro +2

A large number of NP-hard graph problems become polynomial-time solvable on graph classes where the mim-width is bounded and quickly computable. Hence, when solving such problems o…

List k-Colouring Pt​-Free Graphs: a Mim-width Perspective

Colouring (sP1​+P5​)-Free Graphs: a Mim-Width Perspective

Bounding the Mim-Width of Hereditary Graph Classes

List $k$ -Colouring $P_{t}$ -Free Graphs: a Mim-width Perspective

Colouring $(s P_{1} + P_{5})$ -Free Graphs: a Mim-Width Perspective