Graph Structure and Algorithms
Responsable et prÃ©sident:
Kathie Cameron (Wilfrid Laurier University)
[
PDF]
 KATHIE CAMERON, Wilfrid Laurier University
SameDegree Trees and Intermediate Trees [PDF]

Let $G$ be a simple graph whose vertices are labeled. We consider the following questions. (1) Given a spanning tree $T$ of $G$, is there another spanning tree of $G$ with exactly the same degree at each vertex as $T$? (2) Given two spanning trees of $G$, is there another spanning tree of $G$ in which the degree of each vertex is between its degrees in the two given trees? Some of this is joint work with Joanna Fawcett.
 JESSICA ENRIGHT, University of Glasgow
On List Colouring and List Homomorphism of Permutation and Interval Graphs [PDF]

List colouring is an NPcomplete decision problem even if the total number of colours is three. It is hard even on planar bipartite graphs. We give a sketch of a polynomialtime algorithm for solving list colouring of permutation graphs with a bounded total number of colours. This generalises to a polynomialtime algorithm that solves the listhomomorphism problem to any fixed target graph for a large class of input graphs including all permutation and interval graphs.
 ELAINE ESCHEN, West Virginia University
Colored Graph Completion [PDF]

Given a proper vertexcolored graph $G$, the $\Pi$ {\em colored graph completion problem} asks whether there exists a properly colored edgesupergraph of $G$ that has property $\Pi$. We classify the complexity of the circulararc $k$colored graph completion problem, for all fixed $k \geq 1$. Surprisingly, the 3colored case is hard. To our knowledge, this is the first such 3colored graph completion problem that is known to be hard. We also show that the strongly chordal 3colored graph completion problem can be solved in O($n^2$) time (yielding the completion when it exists). (Joint with K. Cook, R. Sritharan, X. Wang)
 R. SRITHARAN, The University of Dayton
Hendry's conjecture holds for spider intersection graphs [PDF]

Hendry conjectured in 1990 that for a nonHamiltonian cycle $C$ in
a Hamiltonian chordal graph, there exists a cycle $C'$ such that $V(C) \subseteq V(C')$
and $V(C') = V(C) + 1$; the conjecture is open. A {\em spider} is a
subdivision of a $K_{1, r}$, $r \geq 0$. A {\em spider intersection graph}
is the intersection graph of subtrees of a spider. We prove Hendry's
conjecture for the class of spider intersection graphs. This result extends
previously known results for interval graphs and split graphs. (Joint work
with Atif Abueida and Arthur Busch)
 KATIE TSUJI, University of Waterloo
Finding Monotone Path Systems in Regions with Holes [PDF]

A monotone path system (MPS) is a finite set of pairwisedisjoint paths (polygonal arcs) in the plane such that every horizontal line intersects each of the paths in at most one point. Consider a simple polygon in the $xy$plane which bounds the polygonal region $D$. Let $T$ and $B$ be two finite, disjoint, equicardinal sets of points of $D$. Cameron and Sachs gave a polynomialtime algorithm to find a MPS whose top points are $T$ and whose bottom points are $B$, or to determine that no such MPS exists. We consider polygonal regions with holes. Joint work with Kathie Cameron.