J. P. Gollin

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 $k \in N$ , every graph $G$ contains $k$ vertex-disjoint cycles of different lengths, or there exists a set $X \subseteq V (G)$ with $|X| \in \mathcal…

Tree-independence number of $P_{5}$ -free graphs with no large bicliques

Václav Blažej, J. Pascal Gollin, Tomáš Hons +5

The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bo…

Tree-independence number and forbidden induced subgraphs: excluding a $6$ -vertex path and a $(2, t)$ -biclique

Maria Chudnovsky, Julien Codsi, J. Pascal Gollin +2

We show that for every positive integer $t \geq 2$ there exists an integer $s$ such that every graph that contains no induced subgraph isomorphic to either the $6$ -vertex path or…

Minimal toughness in subclasses of weakly chordal graphs

J. Pascal Gollin, Martin Milanič, Laura Ogrin

The toughness of a graph $G$ is defined as the largest real number $t$ such that for any set $S \subseteq V (G)$ such that $G - S$ is disconnected, $S$ has at least $t$ times more elem…

Dominated balanced separators in wheel-induced-minor-free graphs

Maria Chudnovsky, J. Pascal Gollin, Matjaž Krnc +1

Gartland and Lokshtanov conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator, that is, a separator whose deletion leaves every…

On ${k}$ -Roman graphs: complexity of recognition and the case of split graphs

Kenny Bešter Štorgel, Nina Chiarelli, Lara Fernández +4

For a positive integer $k$ , a ${k}$ -Roman dominating function of a graph $G = (V, E)$ is a function $f : V \to {0, 1, \dots, k}$ satisfying $\sum_{u\in N(v)} f(u) \geq…

The Erdős-Pósa property for circle graphs as vertex-minors

Rutger Campbell, J. Pascal Gollin, Meike Hatzel +4

We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$ , there exists an integer $t = t (k, H)$ so that every graph $G$ either has a vertex-minor…

On graphs with a simple structure of maximal cliques

J. Pascal Gollin, Meike Hatzel, Sebastian Wiederrecht

We say that a hereditary graph class $G$ is \emph{clique-sparse} if there is a constant $k = k (G)$ such that for every graph $G \in G$ , every vertex of $G…

Wild generalised truncation of infinite matroids

J. Pascal Gollin, Attila Joó

For $n \in N$ , the $n$ -truncation of a matroid $M$ of rank at least $n$ is the matroid whose bases are the $n$ -element independent sets of $M$ . One can extend this defin…

Treewidth, Hadwiger Number, and Induced Minors

Rutger Campbell, James Davies, Marc Distel +7

Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which large treewidth implies the existence o…

Clustered Colouring of Graph Products

Rutger Campbell, J. Pascal Gollin, Kevin Hendrey +5

A colouring of a graph $G$ has clustering $k$ if the maximum number of vertices in a monochromatic component equals $k$ . Motivated by recent results showing that many natural graph…

Optimal bounds for zero-sum cycles. I. Odd order

Rutger Campbell, J. Pascal Gollin, Kevin Hendrey +1

For a finite (not necessarily Abelian) group $(Γ, \cdot)$ , let $n (Γ) \in N$ denote the smallest positive integer $n$ such that for every labelling of the arcs of the comple…

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. M…

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 $G$ . Initially, there is one unit of t…