19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
A Linear Time Algorithm for $7$-$[3]$coloring Triangle-free Hexagonal Graphs
Presented by Dr. Rafal WITKOWSKI
Type: Oral presentation
Track: Coloring of Graphs
Content
Given a graph $G$ and $p \in \mathbb{N}$, a proper $n$-$[p]$coloring is a mapping $f:V(G) \rightarrow 2^{\{1,\ldots,n\}}$
such that $\left\vert f(v)\right\vert = p$ for any vertex $v\in V(G)$ and $f(v)\cap f(u)=\emptyset$ for any pair of adjacent
vertices $u$ and $v$. A $n$-$[p]$coloring is a special case of a multicoloring. Finding a multicoloring of induced subgraphs of the
triangular lattice (called \emph{hexagonal graphs}) has important applications in cellular networks. In this talk we present a
linear algorithm for 7-[3]coloring of triangle-free hexagonal graphs , which solves the open problem stated by Sau,
\v{S}parl and \v{Z}erovnik (2010) and improves the result of Sudeep and Vishwanathan (2005), who proved the existence of a 14-[6]coloring.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Dr. Petra ŠPARL IMFM Ljubljana and University of Maribor, Slovenia
- Prof. Janez ŽEROVNIK IMFM Ljubljana and University of Ljubljana, Slovenia