# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, May 4, 2009

Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

### Conflict-free colorings of graphs and hypergraphs

Abstract:
It is shown that, for any $\epsilon > 0$, every graph of maximum degree $\Delta$ permits a {\em conflict-free coloring} with at most $\log^{2+\epsilon}\Delta$ colors, that is, a coloring with the property that the neighborhood $N(v)$ of any vertex $v$, contains an element whose color differs from the color of any other element of $N(v)$. We give an efficient deterministic algorithm to find such a coloring, based on an algorithmic version of the Lov\'asz Local Lemma suggested by Beck, Molloy and Reed. We need to correct a small error in the Molloy-Reed approach, restate it in a deterministic form, and re-prove it

The problem can be extended to arbitrary hypergraphs $H$: a coloring of the vertices of $H$ is called {\em conflict-free} if each hyperedge $E$ of $H$ contains a vertex whose color does not get repeated in $E$. Every hypergraph with fewer than ${s \choose 2}$ edges permits a conflict-free coloring with fewer than $s$ colors, and this bound cannot be improved. Moreover, there is a linear time deterministic algorithm for finding such a coloring. The concept of conflict-free colorings was first raised in a geometric setting in connection with frequency assignment problems for cellular networks.

Joint work with G\'abor Tardos.

Colloquium - 16:00

### Fixed-parameter tractability and lower bounds for stabbing problems

Abstract:
In addition to approximation algorithms, parameterized complexity theory is a well-known approach when dealing with NP-hard (optimization) problems. The central definition of fixed parameter tractability expresses that the corresponding decision problem can be solved in time O(f(k)n^c), where k is the parameter, e.g., the size of the solution, c is a constant independent of k, and f is an arbitrary computable function. Only recently, one has begun to apply this theory to a geometric context.
In this talk, we will analyze several variants of geometric stabbing problems from a parameterized complexity point of view. In particular, we will show that the problem of stabbing unit-squares with lines does not allow an fpt algorithm when parameterized with the size of the solution (under standard complexity-theoretic assumptions). Still, we will consider some restrictions of the general problem for which such algorithms can be found. Finally, several open problems that arise from geometric settings are presented.

### On the Generalized Girth of Cycle Powers

Abstract:
For a graph $G$ and $d\in \mathbb N,$ the $d$-girth $g_d(G)$ of $G$ is the minimum order of an induced subgraph of $G$ of minimum degree at least $d$ (or $\infty,$ if no such subgraph exists). The $2$-girth of a graph is the same as its usual girth (the length of a shortest cycle), so the $d$-girth is a generalization of the girth. In particular, we examine the $(d+k)$-girth of $C_n^d,$ the $d$-th power of a cycle of length $n.$ This is motivated by a conjecture of K{\'e}zdy and Markert, that $C_n^d$ are the $2d$-regular graphs with largest $(d+1)$-girth. In 1989 Bermond and Peyrat proved $g_{d+k}(C_n^d)\geq \frac{d+k}{2d}$ for $1\leq k\leq d$ which is best-possible for even $d+k,$ but not for odd $d+k.$ In order to improve these results, we reduced the problem of computing $g(d,k):=\inf \left\{ g_{d+k}(C_n^d)/n ~|~n\geq 3 \right\}$ to a minimum mean cycle problem. From the obtained data, we could conclude a general conjecture concerning the $(d+k)$-girth of $C_n^d$ for odd values of $d+k.$ We proved this conjecture for $k=d-3.$

Letzte Aktualisierung: 28.04.2009