CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Graph structure and algorithms
Responsable et président: Kathie Cameron (Wilfrid Laurier University)

KATHIE CAMERON, Wilfrid Laurier University
Recognizing and Colouring Even-Hole-Free Apple-Free 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 apple-free even-hole-free graphs can be decomposed by clique cutsets into, essentially, unit circular-arc 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 even-hole-free graphs (O($n^{11}$)). Colouring apple-free graphs is NP-hard and the complexity of colouring even-hole-free graphs is unknown, but our algorithm colours apple-free even-hole-free 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 (even-hole, 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. Even-hole-free graphs can be decomposed by 2-joins 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
Polynomial-time efficient domination on ($P_6, house)$-free graphs and $(P_6, bull)$-free graphs  [PDF]

The NP-completeness of the Efficient Domination(ED) problem on chordal graphs and claw-free graphs implies: if $F$ is not a linear forest, ED is NP-complete 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 hole-free. (With A. Brandst\"adt, E. Friese)

SHENWEI HUANG, Simon Fraser University
Bounding Clique-width 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 clique-width of $(H_1,H_2)$-free graphs and present three new classes of $(H_1,H_2)$-free graphs of bounded clique-width. 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 semi-orders. 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.


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é Saskatchewan