
On the dichromatic number of surfaces
In this paper, we give bounds on the dichromatic number χ⃗(Σ) of a surfa...
read it

On sensitivity in bipartite Cayley graphs
Huang proved that every set of more than half the vertices of the ddime...
read it

Ample completions of OMs and CUOMs
This paper considers completions of COMs (complexes oriented matroids) t...
read it

Plattenbauten: Touching Rectangles in Space
Planar bipartite graphs can be represented as touching graphs of horizon...
read it

Enumerating karcconnected orientations
We give simple algorithms to enumerate the αorientations of a graph G i...
read it

On the DjokovićWinkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs
It was recently pointed out that certain SiO_2 layer structures and SiO_...
read it

Twodimensional partial cubes
We investigate the structure of twodimensional partial cubes, i.e., of ...
read it

Flip distances between graph orientations
Flip graphs are a ubiquitous class of graphs, which encode relations ind...
read it

The queuenumber of posets of bounded width or height
Heath and Pemmaraju conjectured that the queuenumber of a poset is boun...
read it

The queuenumber of planar posets
Heath and Pemmaraju conjectured that the queuenumber of a poset is boun...
read it

The interval number of a planar graph is at most three
The interval number of a graph G is the minimum k such that one can assi...
read it

Cuts in matchings of 3edgeconnected cubic graphs
We discuss relations between several known (some false, some open) conje...
read it

Computing metric hulls in graphs
We prove that, given a closure function the smallest preimage of a close...
read it

Decomposing 4connected planar triangulations into two trees and one path
Refining a classical proof of Whitney, we show that any 4connected plan...
read it
Kolja Knauer
is this you? claim profile