19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

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

Primary authors

More

Co-authors

More