115 citations · 203 across the 24 of their papers we have counts for
5 papers · 1 filter
On a Ramsey-type problem of Erdős and Pach
Ross J. Kang, Eoin Long, Viresh Patel +1
In this paper we show that there exists a constant such that for any graph on vertices either or its complement has an induced subgraph on ver…
Parameterized TSP: Beating the Average
Gregory Gutin, Viresh Patel
In the Travelling Salesman Problem (TSP), we are given a complete graph together with an integer weighting on the edges of , and we are asked to find a Hamilton cycl…
Finding Shortest Paths between Graph Colourings
Matthew Johnson, Dieter Kratsch, Stefan Kratsch +2
The -colouring reconfiguration problem asks whether, for a given graph , two proper -colourings and of , and a positive integer , there exists a sequence…
A precise threshold for quasi-Ramsey numbers
Ross J. Kang, János Pach, Viresh Patel +1
We consider a variation of Ramsey numbers introduced by Erdős and Pach (1983), where instead of seeking complete or independent sets we only seek a -homogeneous set, a vertex su…
A domination algorithm for -instances of the travelling salesman problem
Daniela Kühn, Deryk Osthus, Viresh Patel
We present an approximation algorithm for -instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we giv…