5 papers
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…
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…
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…
Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets
Tim Planken, Torsten Ueckerdt
A range family is a family of subsets of , like all halfplanes, or all unit disks. Given a range family , we consider the -uniform range…
Shallow Hitting Edge Sets in Uniform Hypergraphs
Tim Planken, Torsten Ueckerdt
A subset of the edges of a graph or hypergraph is hitting if covers each vertex of at least once, and is -shallow if it covers each vertex of at most tim…