Graphs and Combinatorial Geometry
[
PDF]
 DAVID HERSCOVICI, Quinnipiac University
Optimal Pebbling in Hypercubes using Errorcorrecting 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 errorcorrecting 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 2dimensional (barjoint) frameworks in purely combinatorial terms, while the corresponding characterisation in 3dimensions remains a hard open problem. In this talk we will show that such characterisations are possible on frameworks constrained to certain 2dimensional 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 4edgecolored graph [PDF]

Define a ``parallel drawing'' of a $d$edgecolored, $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 3edgecolored 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 4edgecolored graphs.
 JACOBUS SWARTS, Vancouver Island University
The $C_k$extended Graft Construction [PDF]

Gutjahr, Welzl and Woeginger found polynomialtime 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 polynomialtime algorithms, which also work for list homomorphisms. In the process, we are able to extend results of BangJensen and Hell, dealing with homomorphisms to bipartite tournaments, to list homomorphisms.
Handling of online submissions has been provided by the CMS.