Rafał Witkowski & Panos Giannopoulos

Govorita:

Rafał Witkowski (Adam Mickiewicz U, Poland): Graph multicoloring in frequency assignment problem.

Panos Giannopoulos (FU Berlin, Germany): Parameterized complexity of geometric problems: recent results and trends.

 

Abstract of Rafał Witkowski: Given a graph $G$ and a demand function $p:V(G)\rightarrow \mathbb{N} $, a proper $n$-[$p$]\emph{coloring} is a mapping $f:V(G)\rightarrow \{1,\ldots,n\}$ such that $\left\vert f(v)\right\vert \geq p(v)$ for any vertex $v\in V(G)$ and $f(v)\cap f(u)=\emptyset$ for any pair of adjacent vertices $u$ and $v$. The least integer $n$ for which a proper $n$ -[$p$]coloring exists, $\chi_{p}(G)$, is called the \emph{multichromatic number} of $G$. Finding the multichromatic number of induced subgraphs of the triangular lattice (called \emph{hexagonal graphs}) has important applications in cellular networks. The \emph{weighted clique number} of a graph $G$, $\omega_{p}(G)$, is the maximum weight of a clique in $G$, where the \emph{weight} of a clique is the total demand of its vertices. McDiarmid and Reed conjectured that ${\chi}_{p}(G)\leq(9/8){\omega}_{p}(G)+O(1)$ for triangle-free hexagonal graphs. During the talk we talk about algorithm for frequency assignment problem, which is strongly connected to multicoloring of hexagonal graphs. We also show how to prove cDiarmid and Reed conjecture for large and wellknown subclass of triangle-free hexagonal graphs.