CanaDAM 2013
Université Memorial de Terre-Neuve, 10 - 13 juin 2013

Graph Theory IV
Président: Susanna Ferreri (Brock University)

MICHAEL BARRUS, Brigham Young University
Realization polytopes for the degree sequence of a graph  [PDF] [SLIDES]

We introduce two convex polytopes associated with the set of labeled realizations of the degree sequence of a graph. The first is the set of points satisfying inequalities arising naturally from the degree sequence; the second is the convex hull of the points corresponding to the actual realizations. We characterize graphs for which the two polytopes coincide and describe the extra conditions necessary for the convex hull when the polytopes differ. We conclude by showing how aspects of the polytope skeletons compare to properties of the realization graph of the degree sequence.

SUSANNA FERRERI, Brock University

The conjecture that every planar graphs is acyclically 5-choosable [Borodin et al., 2002] has been verified for several restricted classes of graphs. Recently, Borodin and Ivanova, [2011], proved that planar graphs are acyclically 5-choosable if they do not contain i-cycles adjacent to j-cycles, where $3\leq j\leq 5$ if $i=3$ and $4\leq j\leq 6$ if $i=4$. This work improves that result and proves that every planar graph without an i-cycle adjacent to a j-cycle with $3\leq j\leq 5$ if $i=3$ and $4\leq j\leq 5$ if $i=4$ is acyclically 5-choosable. This work is a joint project with Babak Farzad.

HENRY MARTYN MULDER, Econometrisch Instituut, Erasmus Universiteit
Location functions on graphs: why is anonymity an issue?  [PDF] [SLIDES]

A location function on a graph $G = (V, E)$ is a function on the set $V^*$, of all finite sequences of vertices of $V$, to nonempty subsets of $V$, which minimizes some criterion of remoteness. Axiomatic characterizations of these functions have been established only for very special cases. We focus on the median function: the sum of the distances to the elements of the sequence is minimized. Three simple axioms characterize this function on median graphs: anonymity, betweennes and consistency. These axioms are independent. Surprisingly, the independence of anonymity is absloutely non-trivial. We present related results as well.

DAVID RICHTER, Western Michigan University
Combinatorial gluings of outerplanar graphs  [PDF] [SLIDES]

The result of an edge unfolding of a convex polyhedron along a maximal tree is an outerplanar graph with no cut vertices and an even number of outer edges. We address the related question of when such a graph admits a gluing yielding a polyhedral graph. (By Steinitz's theorem, these are the simple, planar, and 3-connected graphs.) The answer seems easiest to understand when the graph is maximal outerplanar, but the general question remains unanswered.

ASIYEH SANAEI, Brock University
Three-colourability of planar graphs without 5-cycles and triangular 3- and 6-cycles  [PDF] [SLIDES]

Steinberg's conjecture (1976) asserts that every planar graph without 4- and 5-cycles is 3-colourable. Despite several attempts, the conjecture remains unsettled, and the relaxations of the problem including avoiding a certain collection of cycles of short lengths are considered. Among many other things, it is known that planar graphs without adjacent triangles and without 5- and 7-cycles are 3-colourable. We make an improvement to this result by showing that planar graphs without 5-cycles and without triangles adjacent to 3- and 6-cycles are 3-colourable.


Joint work with Babak Farzad.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Memorial de Terre-Neuve