Graph structure and algorithms
Organizer and Chair: Kathie Cameron (Wilfrid Laurier University)
[PDF]

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.