3 papers
math.CO2026
A Tutte-type canonical decomposition of 3- and 4-connected graphs
Jan Kurkofka, Tim Planken
We provide a unique decomposition of every 4-connected graph into parts that are either quasi-5-connected, cycles of triangle-torsos and 3-connected torsos on vertices, ge…
math.CO2026
A characterisation of all vertex-transitive finite graphs of connectivity < 5
Jan Kurkofka, Tim Planken
We characterise all vertex-transitive finite connected graphs as essentially 5-connected or on a short list of explicit graph-classes. Our proof heavily uses Tutte-type canonical d…
cs.DS2025
A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
Romain Bourneuf, Tim Planken
The block-cut tree decomposes a connected graph along its cutvertices, displaying its 2-connected components. The Tutte-decomposition extends this idea to 2-separators in 2-connect…