5 papers
Multiway -Cut is fixed-parameter tractable
Tony Huynh, Eun Jung Kim, Sang-il Oum +2
A connectivity function on a finite set is a function that is submodular and symmetric, with . Given a connectivity function via…
An ErdÅs-Pósa theorem for cycles and faces of distinct lengths
J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6
We show that for every , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
Rainbow triangles and the ErdÅs-Hajnal problem in projective geometries
Carolyn Chun, James Dylan Douthitt, Wayne Ge +3
We formulate a geometric version of the ErdÅs-Hajnal conjecture that applies to finite projective geometries rather than graphs, in both its usual 'induced' form and the multicolo…
Sharing tea on a graph
J. Pascal Gollin, Kevin Hendrey, Hao Huang +6
Motivated by the analysis of consensus formation in the Deffuant model for social interaction, we consider the following procedure on a graph . Initially, there is one unit of t…
A coarse ErdÅs-Pósa theorem
Jungho Ahn, J. Pascal Gollin, Tony Huynh +1
An induced packing of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We generalise the classic ErdÅs-Pósa theorem to induced packings of cycles.…