KNAUER , Kolja

We prove that, given a closure function the smallest preimage of a closed set can be calculated in polynomial time in the number of closed sets. This implies that there is a polynomial time algorithm to compute the convex hull number of a graph, when all its convex subgraphs are given as input. We then show that deciding if the smallest...

In this paper, we give bounds on the dichromatic number − → χ (Σ) of a surface Σ, which is the maximum dichromatic number of an oriented graph embeddable on Σ. We determine the asymptotic behaviour of − → χ (Σ) by showing that there exist constants a1 and a2 such that, a1 √ −c log(−c) ≤ − → χ (Σ) ≤ a2 √ −c log(−c) for every surface Σ with Euler...

In this paper, we give bounds on the dichromatic number $\vec{\chi}(\Sigma)$ of a surface $\Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $\Sigma$. We determine the asymptotic behaviour of $\vec{\chi}(\Sigma)$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1\frac{\sqrt{-c}}{\log(-c)}...

In this paper, we give bounds on the dichromatic number χ(Σ) of a surface Σ, which is the maximum dichromatic number of an oriented graph embeddable on Σ. We determine the asymptotic behaviour of χ(Σ) by showing that there exist constants a 1 and a 2 such that, a 1 √ −c log(−c) χ(Σ) a 2 √ −c log(−c) for every surface Σ with Euler characteristic...