CanaDAM 2013 Université Memorial de Terre-Neuve, 10 - 13 juin 2013 www.smc.math.ca//2013f

Graph Structure and Algorithms
Responsable et prÃ©sident: Kathie Cameron (Wilfrid Laurier University)
[PDF]

KATHIE CAMERON, Wilfrid Laurier University
Same-Degree 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 NP-complete 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 polynomial-time algorithm for solving list colouring of permutation graphs with a bounded total number of colours. This generalises to a polynomial-time algorithm that solves the list-homomorphism 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 vertex-colored graph $G$, the $\Pi$ {\em colored graph completion problem} asks whether there exists a properly colored edge-supergraph of $G$ that has property $\Pi$. We classify the complexity of the circular-arc $k$-colored graph completion problem, for all fixed $k \geq 1$. Surprisingly, the 3-colored case is hard. To our knowledge, this is the first such 3-colored graph completion problem that is known to be hard. We also show that the strongly chordal 3-colored 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 non-Hamiltonian 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 pairwise-disjoint 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 polynomial-time 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.