1. Linear bounds on treewidth in terms of excluded planar minorsJ. Pascal Gollin, Kevin Hendrey, Sang-il Oum, Bruce Reed, 2025, original scientific article Abstract: 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 considering the maximum integer $k$ such that $H$ contains $k$ vertex-disjoint cycles. There exists a graph of treewidth $\Omega(k\log k)$ which does not contain $k$ vertex-disjoint cycles, from which it follows that $f(H) = \Omega(k\log k)$. In particular, if $f(H)$ is linear in $\lvert V(H) \rvert$ for graphs $H$ from a subclass of planar graphs, it is necessary that $n$-vertex graphs from the class contain at most $\lvert V(H) \rvert$ vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an $n$-vertex graph $H$ which is a disjoint union of $r$ cycles, we show that ${f(H) \leq 3n/2 + O(r^2 \log r)}$, and improve this to $f(H)$≤$n$+O(√$n$) when $r$=2. In particular this bound is linear when $r$=O(√$n$/logn). We present a linear bound for $f(H)$ when $H$ is a subdivision of an $r$-edge planar graph for any constant~$r$. We also improve the best known bounds for $f(H)$ when $H$ is the wheel graph or the 4×4 grid, obtaining a bound of 160 for the latter.
Keywords: graph minor, treewidth, cycle packing
Published in RUP: 05.01.2026; Views: 229; Downloads: 2
 Full text (613,98 KB)
This document has more files! More... |
2. On {k}-Roman graphsKenny Bešter Štorgel, Nina Chiarelli, Lara Fernández, J. Pascal Gollin, Claire Hilaire, Valeria Alejandra Leoni, Martin Milanič, 2025, published scientific conference contribution Abstract: For a positive integer k, a {k}-Roman dominating function of a graph G = (V, E) is a function f : V → {0, 1, . . . , k} satisfying f (N(v)) ≥ k for each vertex v ∈ V with f (v) = 0. Every graph G satisfies γ{Rk}(G) ≤ kγ(G), where γ{Rk}(G) denotes the minimum weight of a {k}-Roman dominating function of G and γ(G) is the domination number of G. In this work we study graphs for which the equality is reached, called {k}-Roman graphs. This extends the concept of {k}-Roman trees studied by Wang et al. in 2021 to gen- eral graphs. We prove that for every k ≥ 3, the problem of recognizing {k}-Roman graphs is NP-hard, even when restricted to split graphs. We provide partial answers to the question of which split graphs are {2}-Roman: we characterize {2}-Roman split graphs that can be decomposed with respect to the split join operation into two smaller split graphs and classify the {k}-Roman property within two specific families of split graphs that are prime with respect to the split join operation: suns and their complements.
Keywords: graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness
Published in RUP: 16.12.2025; Views: 205; Downloads: 2
Full text (395,09 KB)
This document has more files! More... |
3. Optimal bounds for zero-sum cycles. I. Odd orderRutger Campbell, J. Pascal Gollin, Kevin Hendrey, Raphael Steiner, 2025, original scientific article Abstract: For a finite (not necessarily abelian) group Γ, let n(Γ) denote the smallest positive integer $n$ such that for each labelling of the arcs of the complete digraph of order n using elements from Γ, there exists a directed cycle such that the arc-labels along the cycle multiply to the identity. Alon and Krivelevich [2] initiated the study of the parameter n(.) on cyclic groups and proved n(Z_q) = O(q log q). This was later improved to a linear bound of n(Γ) <= 8|Γ| for every finite abelian group Γ by Mészáros and the last author [8], and then further to n(Γ) <= 2|Γ|-1 for every non-trivial finite group independently by Berendsohn, Boyadzhiyska and Kozma [3] as well as by Akrami, Alon, Chaudhury, Garg, Mehlhorn and Mehta [1]. In this series of two papers we conclude this line of research by proving that n(Γ) < |Γ|+1 for every finite group Γ, which is the best possible such bound in terms of the group order and precisely determines the value for all cyclic groups as n(Z_q) = q+1. In the present paper we prove the above result for all groups of odd order. The proof for groups of even order needs to overcome substantial additional obstacles and will be presented in the second part of this series.
Keywords: Zero-sum Ramsey theory, directed cycles, Zero-sum cycles
Published in RUP: 24.11.2025; Views: 290; Downloads: 4
Full text (398,18 KB)
This document has more files! More... |
4. A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groupsJ. Pascal Gollin, Kevin Hendrey, O-joung Kwon, Sang-il Oum, Youngho Yoo, 2025, original scientific article Abstract: In 1965, Erdős and Pósa proved that there is an (approximate) 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 1988 to find all pairs (l, z) of integers where such a duality holds for the family of cycles of length l modulo z. We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface.
Keywords: Erdős-Pósa property, cycle packing, group-labelled graph
Published in RUP: 17.11.2025; Views: 337; Downloads: 8
Full text (1,17 MB)
This document has more files! More... |
5. |
