5 papers · 1 filter
Path decompositions of random directed graphs
Alberto Espuny Díaz, Viresh Patel, Fabian Stroh
We consider the problem of decomposing the edges of a directed graph into as few paths as possible. There is a natural lower bound for the number of paths needed in an edge decompo…
Switch-based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs
Pieter Kleer, Viresh Patel, Fabian Stroh
We consider the irreducibility of switch-based Markov chains for the approximate uniform sampling of Hamiltonian cycles in a given undirected dense graph on vertices. As our ma…
A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
Viresh Patel, Fabian Stroh
We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given , there exists a such that the fo…
Structure and colour in triangle-free graphs
N. R. Aravind, Stijn Cambie, Wouter Cames van Batenburg +3
Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number contains a rainbow independent set of size $…
Decomposing tournaments into paths
Allan Lo, Viresh Patel, Jozef Skokan +1
We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomp…