9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

Threshold coloring and unit cube contact representation of graphs

Presented by Gašper FIJAVž
Type: Oral presentation
Track: Graph Theory

Content

Given a partition of edges of a graph $G$ into \emph{near} and \emph{far} edges, a \emph{threshold coloring} is a labeling of $V(G)$ so that every pair of vertices adjacent with a \emph{near} edge receive integer labels that are closer than a certain threshold, and every pair of vertices adjacent with a \emph{far} edge receive labels at greater distance. Not every planar graph is threshold colorable, yet several subclasses of planar graphs admit a threshold coloring. Applying the concept of threshold colorings to infinite planar grids we were able to show that, for example, every subgraph of a hexagonal tessellation of the plane admits a unit-cube contact representation.

Place

Location: Koper, Slovenia

Primary authors

More