DAVID HERSCOVICI, Quinnipiac University
Optimal Pebbling in Hypercubes using Error-correcting codes  [PDF]

A \emph{pebbling distribution} on a graph $G$ consists of placing pebbles on $V(G)$. A \emph{pebbling move} removes two pebbles from some vertex and adds one pebble to an adjacent vertex. A distribution is \emph{solvable} if a pebble can be moved to any target vertex by a sequence of pebbling moves. Using error-correcting codes, we construct solvable distributions on hypercubes $Q^n$ where the number of pebbles is in $O(1.34^n)$, improving on previously constructed distributions.

TONY NIXON, Lancaster University
Combinatorial Rigidity on Surfaces  [PDF]

Laman's theorem provides a characterisation of minimally rigid generic 2-dimensional (bar-joint) frameworks in purely combinatorial terms, while the corresponding characterisation in 3-dimensions remains a hard open problem. In this talk we will show that such characterisations are possible on frameworks constrained to certain 2-dimensional surfaces. The key step we will discuss is to provide inductive constructions of the classes of [2,l]-tight graphs (for l=1,2,3).

DAVID RICHTER, Western Michigan University
How to draw a 4-edge-colored graph  [PDF]

Define a ``parallel drawing'' of a $d$-edge-colored, $d$-regular graph a drawing in the plane such that (a) every vertex is represented by a point, (b) every edge is represented by a segment, and (c) the edges sharing a common color are parallel. The 3-edge-colored graphs which admit a faithful projective drawing were recently completely characterized. The purpose here is to explain the complications when one considers the corresponding problem for 4-edge-colored graphs.

JACOBUS SWARTS, Vancouver Island University
The $C_k$-extended Graft Construction  [PDF]

Gutjahr, Welzl and Woeginger found polynomial-time algorithms for a number of digraph homomorphism problems. These algorithms are based on the \underbar{$X$}-enumeration, the $C_k$-extended \underbar{$X$}-enumeration and the \underbar{$X$}-graft construction. In this talk, we show how the last two methods can be combined to obtain new polynomial-time algorithms, which also work for list homomorphisms. In the process, we are able to extend results of Bang-Jensen and Hell, dealing with homomorphisms to bipartite tournaments, to list homomorphisms.

Handling of online submissions has been provided by the CMS.