Zobrazeno 1 - 10
of 521
pro vyhledávání: '"J. Pascal"'
Autor:
Campbell, Rutger, Davies, James, Distel, Marc, Frederickson, Bryce, Gollin, J. Pascal, Hendrey, Kevin, Hickingbotham, Robert, Wiederrecht, Sebastian, Wood, David R., Yepremyan, Liana
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 of a large complete graph minor. To formalise this, we say that a graph
Externí odkaz:
http://arxiv.org/abs/2410.19295
Autor:
Campbell, Rutger, Gollin, J. Pascal, Hendrey, Kevin, Lesgourgues, Thomas, Mohar, Bojan, Tamitegama, Youri, Tan, Jane, Wood, David R.
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 classes are subgraphs of the strong product of a graph with bounded t
Externí odkaz:
http://arxiv.org/abs/2407.21360
An \emph{induced packing} of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We generalise the classic Erd\H{o}s-P\'osa theorem to induced packings of cycles. More specifically, we show that there exists a function ${
Externí odkaz:
http://arxiv.org/abs/2407.05883
For a finite (not necessarily Abelian) group $(\Gamma,\cdot)$, let $n(\Gamma) \in \mathbb{N}$ denote the smallest positive integer $n$ such that for every labelling of the arcs of the complete digraph of order $n$ using elements from $\Gamma$, there
Externí odkaz:
http://arxiv.org/abs/2406.19855
Autor:
Gollin, J. Pascal, Hendrey, Kevin, Huang, Hao, Huynh, Tony, Mohar, Bojan, Oum, Sang-il, Yang, Ningyuan, Yu, Wei-Hsuan, Zhu, Xuding
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 tea at a fixed vertex $r \in V(G)$, and all other vertices have no tea.
Externí odkaz:
http://arxiv.org/abs/2405.15353
One of the fundamental results in graph minor theory is that for every planar graph $H$, there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to $H$ have treewidth at most $f(H)$. A lower bound for ${f(H)}$ can be obtained by c
Externí odkaz:
http://arxiv.org/abs/2402.17255
We investigate a structural generalisation of treewidth we call $\mathcal{A}$-blind-treewidth where $\mathcal{A}$ denotes an annotated graph class. This width parameter is defined by evaluating only the size of those bags $B$ of tree-decompositions f
Externí odkaz:
http://arxiv.org/abs/2304.04504
Autor:
Gollin, J. Pascal, Joó, Attila
A fundamental result in linear algebra states that if a homogenous linear equation system has only the trivial solution, then there are at most as many variables as equations. We prove the following generalisation of this phenomenon. If a possibly in
Externí odkaz:
http://arxiv.org/abs/2211.12917
Autor:
Campbell, Rutger, Distel, Marc, Gollin, J. Pascal, Harvey, Daniel J., Hendrey, Kevin, Hickingbotham, Robert, Mohar, Bojan, Wood, David R.
A graph class $\mathcal{G}$ has linear growth if, for each graph $G \in \mathcal{G}$ and every positive integer $r$, every subgraph of $G$ with radius at most $r$ contains $O(r)$ vertices. In this paper, we show that every graph class with linear gro
Externí odkaz:
http://arxiv.org/abs/2210.13720
In 1965, Erd\H{o}s and P\'{o}sa proved that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in
Externí odkaz:
http://arxiv.org/abs/2209.09488