Graph Structure and Algorithms II
Org: Kathie Cameron and Shenwei Huang
(Wilfrid Laurier University / University of New South Wales)
- KATHIE CAMERON, Wilfrid Laurier University
Solving the clique cover problem on (bull, $C_4$)-free graphs [PDF]
For the class of (bull, $C_4$)-free graphs, a largest clique can be found in polynomial time, but stability number and chromatic number are NP-hard. We give a polynomial-time algorithm to find a minimum clique cover of a (bull, $C_4$)-free graph, or equivalently, a minimum colouring of a (bull, $2K_2$)-free graph. (Bull, $2K_2$)-free graphs are AT-free. The complexity of colouring AT-free graphs is a long-standing open problem, although Stacho has given a polynomial-time algorithm for 3-colouring them and Kratsch and M\"uller have given a polynomial-time algorithm for $k$-colouring them for fixed $k$. This is joint work with Ch\'inh T. Ho\`ang.
- ELAINE ESCHEN, West Virginia University
Colored graph completion problem for classes of chordal graphs [PDF]
The $\Pi$-Colored Graph Completion ($\Pi$-CGC) problem asks whether a graph properly vertex-colored with $k$ colors ($k$ either constant or arbitrary) can be completed by adding edges to have property $\Pi$, while maintaining the proper coloring. We present an O($n^2$)-time algorithm for strongly chordal CGC when $k = 3$; it is NP-complete when $k$ is arbitrary. When $k = 3$, there are efficient algorithms for interval graph CGC and chordal CGC. Our result nests in a structural hierarchy of characterizations of when a graph admits an interval completion, strongly chordal completion, or chordal completion. Joint work with R. Sritharan, X. Wang.
- PAVOL HELL, Simon Fraser University
Digraph Analogues of Nice Graph Classes [PDF]
I will discuss some recently studied classes of digraphs that are natural analogues of popular graph classes, including analogues of split graphs, interval graphs, and chordal graphs. In each case, the digraph class extends the corresponding graph class, admits a polynomial recognition algorithm, and a structural obstruction characterization. In some classes, natural problems that are NP-complete for general digraphs can be solved in polynomial time. Open problems will be presented. This reports on joint work with T. Feder. C. Hernandez Cruz, J. Huang, and A. Rafiey.
- CHINH HOANG, Wilfrid Laurier University
Coloring graphs without small forbidden subgraphs [PDF]
Given a set $L$ of graphs, a graph $G$ is $L$-free if $G$ does not
contain any graph in $L$ as an induced subgraph. There has been
keen interest in coloring graphs, in polynomial time, whose forbidden list $L$
contains graphs with four vertices. The state of the art on this problem identifies three
outstanding classes: $L=(4K_1$, claw), $L=(4K_1$, claw,
co-diamond), and $L=(4K_1, C_4$). We will discuss these three open problems in our talk.
- R. SRITHARAN, University of Dayton
Graph modification problem [PDF]
We consider the problems of only adding, only deleting, or adding as well as deleting the
fewest number of edges to/from a given graph to obtain a graph with a specified property.
We discuss the complexity of these problems for the property of membership in a variety
of graph classes. Of particular note are the problems for chordal bipartite graphs that had