Contact representations of graphs have a long history. Most research has focused on
problems in 2d, but 3d contact representations have also been investigated, mostly …

We present a deterministic fully-dynamic data structure for maintaining information about the
bridges in a graph. We support updates in Õ ((log n) 2) amortized time, and can find a bridge …

We give an efficient algorithm that, given a graph G and a partition V1,…, Vm of its vertex set,
finds either an independent transversal (an independent set {v1,…, vm} in G such that has a …

Petersen's theorem, one of the earliest results in graph theory, states that any bridgeless
cubic multigraph contains a perfect matching. While the original proof was neither …

The Cycle double cover (CDC) conjecture states that for every bridgeless graph G, there
exists a family F of cycles such that each edge of the graph is contained in exactly two …

To determine the spectrum of Steiner quadruple systems (SQS) admitting a specific
automorphism group is of great interest in design theory. We consider a strictly cyclic SQS …

We give a fast algorithm for computing an irreducible triangulation T′ of an oriented,
connected, boundaryless, and compact surface S in E d from any given triangulation T of S …

We perform an experimental comparison of four algorithms for converting a given
triangulation T of an orientable, connected, boundaryless, and compact surface S in Ed into …

Perfect matchings and maximum weight matchings are two fundamental combinatorial
structures. We consider the ratio between the maximum weight of a perfect matching and the …

Abstract Given positive integers $ k $, $ q $, we say that a graph is edge $ k $-$ q $-
colorable if its edges can be colored in such a way that the number of colors incident to each …