Dr Viresh Patel

Research

Extremal combinatorics, Probabilistic combinatorics, Graph polynomials / partition functions, Phase transitions, Approximation algorithms (for counting)

Publications of specific relevance to the Centre for Combinatorics, Algebra and Number Theory

Publications of specific relevance to the Centre for Combinatorics, Algebra and Number Theory

2024

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
Jenssen M, Patel V and Regts G
Journal of Combinatorial Theory Series B, Elsevier vol. 169, 233-252.  

DOI 10.1016/j.jctb.2024.06.005

01-11-2024

Hamilton cycles in dense regular digraphs and oriented graphs
Lo A, Patel V and Yıldız MA
Journal of Combinatorial Theory Series B, Elsevier vol. 164, 119-160.  

DOI 10.1016/j.jctb.2023.09.004

01-01-2024

2023

Orthogonal schedules in single round robin tournaments
Lambers R, Briët J, Patel V, Spieksma F and Yıldız MA
Operations Research Letters, Elsevier vol. 51 (5), 528-532.  

DOI 10.1016/j.orl.2023.08.002

01-09-2023

Cycle Partition of Dense Regular Digraphs and Oriented Graphs
Lo A, Patel V and Yildiz MA
Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. (12), 717-724.  

DOI 10.5817/cz.muni.eurocomb23-099

28-08-2023

2022

Approximate counting using Taylor's theorem: a survey
Patel V and Regts G
 

DOI 10.48550/arxiv.2212.08143

QMRO

15-12-2022

A POLYNOMIAL-TIME ALGORITHM TO DETERMINE (ALMOST) HAMILTONICITY OF DENSE REGULAR GRAPHS
Patel V and Stroh F
Siam Journal On Discrete Mathematics, Society For Industrial and Applied Mathematics vol. 36 (2), 1363-1393.  

DOI 10.1137/20M1356191

QMRO

07-06-2022

Sampling from the low temperature Potts model through a Markov chain on flows
Huijben J, Patel V and Regts G
Random Structures and Algorithms, Wiley 

DOI 10.1002/rsa.21089

QMRO

16-04-2022

Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
Buys P, Galanis A, Patel V and Regts G
Forum of Mathematics Sigma, Cambridge University Press (Cup) vol. 10 

DOI 10.1017/fms.2022.4

QMRO

01-01-2022

2021

On zero-free regions for the anti-ferromagnetic potts model on bounded-degree graphs
Bencs F, Davies E, Patel V and Regts G
Annales De L’Institut Henri Poincaré D, Ems Press vol. 8 (3), 459-489.  

DOI 10.4171/AIHPD/108

QMRO

23-09-2021

Structure and colour in triangle-free graphs
Aravind NR, van Batenburg WC, Kang RJ, Cambie S, de Verclos RDJ and Patel V
Journal of Combinatorics, Electronic Journal of Combinatorics vol. 28 (2) 

DOI 10.37236/9267

QMRO

18-06-2021

Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs
Buys P, Galanis A, Patel V and Regts G
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms., 1508-1519.  
01-01-2021

Path Decompositions of Random Directed Graphs
Espuny Díaz A, Patel V and Stroh F
In Extended Abstracts Eurocomb 2021, Springer Nature 702-706.  

DOI 10.1007/978-3-030-83823-2_112

01-01-2021

2020

Switch-Based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs
Kleer P, Patel V and Stroh F
The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics vol. 27 (4) 

DOI 10.37236/9503

13-11-2020

Statistical physics approaches to Unique Games
Coulson M, Davies E, Kolla A, Patel V and Regts G
Leibniz International Proceedings in Informatics, LIPIcs. vol. 169 

DOI 10.4230/LIPIcs.CCC.2020.13

01-07-2020

Decomposing tournaments into paths
Lo A, Patel V, Skokan J and Talbot J
Proceedings of The London Mathematical Society, Wiley vol. 121 (2), 426-461.  

DOI 10.1112/plms.12328

29-04-2020

2019

Discrepancy and large dense monochromatic subsets
Kang RJ, Patel V and Regts G
Journal of Combinatorics, International Press of Boston vol. 10 (1), 87-109.  

DOI 10.4310/joc.2019.v10.n1.a4

01-01-2019

2018

Hamilton Cycles in Sparse Robustly Expanding Digraphs
Lo A and Patel V
The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics vol. 25 (3) 

DOI 10.37236/7418

07-09-2018

Computing the Number of Induced Copies of a Fixed Graph in a Bounded Degree Graph
Patel V and Regts G
Algorithmica, Springer Nature vol. 81 (5), 1844-1858.  

DOI 10.1007/s00453-018-0511-9

05-09-2018

Excluding Hooks and their Complements
Choromanski K, Falik D, Liebenau A, Patel V and Pilipczuk M
The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics vol. 25 (3) 

DOI 10.37236/6397

24-08-2018

2017

On a Ramsey‐type problem of Erdős and Pach
Kang RJ, Long E, Patel V and Regts G
Bulletin of The London Mathematical Society, Wiley vol. 49 (6), 991-999.  

DOI 10.1112/blms.12094

06-10-2017

Decomposing tournaments into paths
Lo A, Patel V, Skokan J and Talbot J
Electronic Notes in Discrete Mathematics, Elsevier vol. 61, 813-818.  

DOI 10.1016/j.endm.2017.07.040

01-08-2017

Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
Patel V and Regts G
Electronic Notes in Discrete Mathematics, Elsevier vol. 61, 971-977.  

DOI 10.1016/j.endm.2017.07.061

01-08-2017

Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
Patel V and Regts G
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 46 (6), 1893-1919.  

DOI 10.1137/16m1101003

01-01-2017

2016

Parameterized Traveling Salesman Problem: Beating the Average
Gutin G and Patel V
Siam Journal On Discrete Mathematics, Society For Industrial & Applied Mathematics (Siam) vol. 30 (1), 220-238.  

DOI 10.1137/140980946

01-01-2016

2015

On a Ramsey-type problem of Erdős and Pach
Kang RJ, Patel V and Regts G
Electronic Notes in Discrete Mathematics, Elsevier vol. 49, 821-827.  

DOI 10.1016/j.endm.2015.06.049

01-11-2015

A domination algorithm for {0,1}‐instances of the travelling salesman problem
Kühn D, Osthus D and Patel V
Random Structures and Algorithms, Wiley vol. 48 (3), 427-453.  

DOI 10.1002/rsa.20600

08-10-2015

Finding Shortest Paths Between Graph Colourings
Johnson M, Kratsch D, Kratsch S, Patel V and Paulusma D
Algorithmica, Springer Nature vol. 75 (2), 295-321.  

DOI 10.1007/s00453-015-0009-7

12-05-2015

Poset limits can be totally ordered
Hladký J, Máthé A, Patel V and Pikhurko O
Transactions of The American Mathematical Society, American Mathematical Society (Ams) vol. 367 (6), 4319-4337.  

DOI 10.1090/s0002-9947-2015-06299-0

03-02-2015

A Precise Threshold for Quasi-Ramsey Numbers
Kang RJ, Pach J, Patel V and Regts G
Siam Journal On Discrete Mathematics, Society For Industrial & Applied Mathematics (Siam) vol. 29 (3), 1670-1682.  

DOI 10.1137/14097313x

01-01-2015

2014

Mixing of the Glauber dynamics for the ferromagnetic Potts model
Bordewich M, Greenhill C and Patel V
Random Structures and Algorithms, Wiley vol. 48 (1), 21-52.  

DOI 10.1002/rsa.20569

04-09-2014

Tight inequalities among set hitting times in Markov chains
Griffiths S, Kang RJ, Oliveira RI and Patel V
Proceedings of The American Mathematical Society, American Mathematical Society (Ams) vol. 142 (9), 3285-3298.  

DOI 10.1090/s0002-9939-2014-12045-4

21-05-2014

Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
Kuehn D, Lapinskas J, Osthus D and Patel V
Proceedings of The London Mathematical Society vol. 109, 733-762.  

DOI 10.1112/plms/pdu019

01-01-2014

Finding Shortest Paths Between Graph Colourings
Johnson M, Kratsch D, Kratsch S, Patel V and Paulusma D
Lecture Notes in Computer Science. vol. 8894, 221-233.  

DOI 10.1007/978-3-319-13524-3_19

01-01-2014

2013

Obtaining Online Ecological Colourings by Generalizing First-Fit
Johnson M, Patel V, Paulusma D and Trunck T
Theory of Computing Systems, Springer Nature vol. 54 (2), 244-260.  

DOI 10.1007/s00224-013-9513-9

07-12-2013

Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
Broersma H, Golovach PA and Patel V
Theoretical Computer Science, Elsevier vol. 485, 69-84.  

DOI 10.1016/j.tcs.2013.03.008

01-05-2013

On Toughness and Hamiltonicity of 2K2‐Free Graphs
Broersma H, Patel V and Pyatkin A
Journal of Graph Theory, Wiley vol. 75 (3), 244-255.  

DOI 10.1002/jgt.21734

19-02-2013

Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
Patel V
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 42 (3), 1113-1131.  

DOI 10.1137/100811416

01-01-2013

Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
Kühn D, Lapinskas J, Osthus D and Patel V
In The Seventh European Conference On Combinatorics, Graph Theory and Applications, Springer Nature 471-476.  

DOI 10.1007/978-88-7642-475-5_75

01-01-2013

2012

The complexity of finding uniform sparsest cuts in various graph classes
Bonsma P, Broersma H, Patel V and Pyatkin A
Journal of Discrete Algorithms. vol. 14, 136-149.  

DOI 10.1016/j.jda.2011.12.008

01-07-2012

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
Bonamy M, Johnson M, Lignos I, Patel V and Paulusma D
Journal of Combinatorial Optimization. vol. 27 (1), 132-143.  

DOI 10.1007/s10878-012-9490-y

26-04-2012

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width
Broersma H, Golovach PA and Patel V
Lecture Notes in Computer Science. vol. 7112, 207-218.  

DOI 10.1007/978-3-642-28050-4_17

01-01-2012

2011

On the diameter of reconfiguration graphs for vertex colourings
Bonamy M, Johnson M, Lignos I, Patel V and Paulusma D
Electronic Notes in Discrete Mathematics, Elsevier vol. 38, 161-166.  

DOI 10.1016/j.endm.2011.09.028

01-12-2011

The Complexity Status of Problems Related to Sparsest Cuts
Bonsma P, Broersma H, Patel V and Pyatkin A
Lecture Notes in Computer Science. vol. 6460, 125-135.  

DOI 10.1007/978-3-642-19222-7_14

01-01-2011

2010

Average relational distance in linear extensions of posets
Brightwell G and Patel V
Discrete Mathematics, Elsevier vol. 310 (5), 1016-1021.  

DOI 10.1016/j.disc.2009.10.016

01-03-2010

Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
Patel V
Lecture Notes in Computer Science. vol. 6346, 561-572.  

DOI 10.1007/978-3-642-15775-2_48

01-01-2010

Obtaining Online Ecological Colourings by Generalizing First-Fit
Johnson M, Patel V, Paulusma D and Trunck T
Lecture Notes in Computer Science. vol. 6072, 240-251.  

DOI 10.1007/978-3-642-13182-0_22

01-01-2010

2008

Partitioning Posets
Patel V
Order, Springer Nature vol. 25 (2), 131-152.  

DOI 10.1007/s11083-008-9085-5

01-05-2008

2007

Cutting two graphs simultaneously
Patel V
Journal of Graph Theory, Wiley vol. 57 (1), 19-32.  

DOI 10.1002/jgt.20274

22-10-2007