Graph structure and algorithms
Organizer and Chair:
Kathie Cameron (Wilfrid Laurier University)
[
PDF]
 KATHIE CAMERON, Wilfrid Laurier University
Recognizing and Colouring EvenHoleFree AppleFree Graphs [PDF]

A hole is an induced cycle with at least four vertices. An apple is a hole with a pendant edge. We prove that applefree evenholefree graphs can be decomposed by clique cutsets into, essentially, unit circulararc graphs. This is the basis for our algorithms for recognizing and colouring these graphs. Our recognition algorithm is more efficient (O($nm$)) than known algorithms for recognizing evenholefree graphs (O($n^{11}$)). Colouring applefree graphs is NPhard and the complexity of colouring evenholefree graphs is unknown, but our algorithm colours applefree evenholefree graphs in O($n^3$) time. This is joint work with Steven Chaplick and Ch\'{i}nh Ho\`{a}ng.
 MURILO DA SILVA, Simon Fraser University
Decomposing (evenhole, bull)free graphs [PDF]

A decomposition theorem for a given graph class C is a characterization
stating that if G belongs to C, then G is either "basic" (has a well understood
structure) or G has a prescribed cutset, along which it can be decomposed.
Evenholefree graphs can be decomposed by 2joins and star cutsets. We discuss
in this talk how imposing more structure, such as forbidding the bull graph,
one can obtain a decomposition using more refined versions of star cutsets.
 ELAINE ESCHEN, West Virginia University
Polynomialtime efficient domination on ($P_6, house)$free graphs and $(P_6, bull)$free graphs [PDF]

The NPcompleteness of the Efficient Domination(ED) problem on chordal graphs and clawfree graphs implies: if $F$ is not a linear forest, ED is NPcomplete on $F$free graphs. For $F$free graphs ($F$ a linear forest), the only remaining open case is the complexity of ED on $P_6$free graphs. We show ED/WeightedED is solvable in polynomial time on $(P_6, house)$free graphs and $(P_6, bull)$free graphs, using a known reduction from ED/WED on $G$ to Maximum Weight Independent Set on $G^2$. Moreover, we show that the square of a $P_6$free graph with an efficient dominating set is holefree. (With A. Brandst\"adt, E. Friese)
 SHENWEI HUANG, Simon Fraser University
Bounding Cliquewidth via Perfect Graphs [PDF]

Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. We continue a recent study into the cliquewidth of $(H_1,H_2)$free graphs and present three new classes of $(H_1,H_2)$free graphs of bounded cliquewidth. The three new graph classes have in common that one of their two forbidden induced subgraphs is the diamond. To prove our results we develop a technique based on bounding clique covering number in combination with reduction to subclasses of perfect graphs.
This is a joint work with Konrad Dabrowski and Daniel Paulusma.
 JERRY SPINRAD, Vanderbilt University
Double Threshold Digraphs [PDF]

Double threshold graphs generalize semiorders. Double threshold graphs use 2 thresholds t1 and t2. If w(x) and w(y) differ by at most t1, x and y must be incomparable. If w(x)w(y) is greater than t2, x must be greater than y. If x exceeds y by an amount between t1 and t2, we may choose x greater than y, or x and y incomparable.
Every directed acyclic graph G can be represented with some minimum ratio t2/t1. We discuss properties of graphs where this ratio is fixed, giving both algorithms and characterizations, and discussing the motivation for studying this property.