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: 255; Downloads: 2
 Full text (613,98 KB)
This document has more files! More... |
2. 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: 341; Downloads: 8
Full text (1,17 MB)
This document has more files! More... |
3. |
4. Primitive, edge-short, isometric, and pantochordal cyclesGover E. C. Guzman, Marcos E. González Laffitte, André Fujita, Peter F. Stadler, 2025, original scientific article Abstract: A cycle in a graph G is said to be primitive from its vertex x if at least one of its edges does not belong to any shorter cycle that passes through x. This type of cycle and an associated notion of extended neighborhoods play a key role in message-passing algorithms that compute spectral properties of graphs with short loops. Here, we investigate such primitive cycles and graphs without long primitive cycles in a more traditional graph-theoretic framework. We show that a cycle is primitive from all its vertices if and only if it is isometric. We call a cycle fully redundant cycles if it is not primitive from any of its vertices and show that fully redundant cycles, in particular, are not edge short, i.e., they cannot be represented as the edge-disjoint union of a single edge and two shortest paths in G. The families Rk and Lk of graphs with all cycles of length at least k + 1 being fully redundant and not edge-short, respectively, coincide for k = 3 and k = 4. In these graphs, all cycles of length at least k + 1 are pantochordal, i.e., each of their vertices is incident with a chord. None of these results generalizes to k ≥ 5. Moreover, R₃ = L₃ turn out to be the block graphs, and R₄ = L₄ are the graphs with complete multi-partite blocks. The cographs, finally, are shown to form a proper subset of R₅.
Keywords: edge-short cycle, chord, block-graph, complete multipartite graph, wheel graphs, cographs, geodesic cycles, Hamiltonian cycles
Published in RUP: 03.11.2025; Views: 240; Downloads: 0
Full text (478,50 KB) |
5. Basic tetravalent oriented graphs of independent-cycle typeNemanja Poznanović, Cheryl E. Praeger, 2025, original scientific article Abstract: The family OG(4) consisting of graph-group pairs (Γ, G), where Γ is a finite, connected, 4-valent graph admitting a G-vertex-, and G-edge-transitive, but not G-arc-transitive action, has recently been examined using a normal quotient methodology. A subfamily of OG(4) has been identified as ‘basic’, due to the fact that all members of OG(4) are normal covers of at least one basic pair. We provide an explicit classification of those basic pairs (Γ, G) which have at least two independent cyclic G-normal quotients (these are G-normal quotients which are not extendable to a common cyclic normal quotient).
Keywords: half-arc-transitive, vertex-transitive graph, edge-transitive graph, normal cover, cycle graph
Published in RUP: 21.10.2025; Views: 335; Downloads: 1
Full text (398,19 KB) |
6. |
7. Hamilton cycles in primitive vertex-transitive graphs of order a product of two primes - the case PSL(2, q[sup]2) acting on cosets of PGL(2, q)Shao Fei Du, Klavdija Kutnar, Dragan Marušič, 2020, original scientific article Abstract: A step forward is made in a long standing Lovász problem regarding hamiltonicity of vertex-transitive graphs by showing that every connected vertex-transitive graph of order a product of two primes arising from the group action of the projective special linear group PSL▫$(2, q^2)$▫ on cosets of its subgroup isomorphic to the projective general linear group PGL$(2, q)$ contains a Hamilton cycle.
Keywords: vertex-transitive graph, Hamilton cycle, automorphism group, orbital graph
Published in RUP: 20.07.2020; Views: 3132; Downloads: 56
Full text (365,31 KB) |
8. |
9. |
10. |
