Graph Structure and Algorithms I
Org:
Kathie Cameron and Shenwei Huang (Wilfrid Laurier University / University of New South Wales)
[
PDF]
 CÉSAR HERNÁNDEZ CRUZ, Universidad Nacional Autónoma de México
Cograph minimal $(s,k)$polar obstructions. [PDF]

A cograph is a $P_4$free graph. A $(s,k)$polar partition
of a graph $G$ is a partition $(A,B)$ of $V(G)$ such that
$G[A]$ is a complete multipartite graph with at most $s$
parts, and $G[B]$ is the disjoint union of at most $k$cliques.
A graph $G$ is $(s,k)$polar if it admits an $(s,k)$polar
partition.
It is known that $(s,k)$polar cographs admit a characterization
through a finite set of minimal obstructions. In this talk we
will discuss the structure of cograph $(2,2)$polar minimal
obstructions, as well as give some insight on the structure
of $(k,k)$minimal obstructions.
 JING HUANG, University of Victoria
Endvertices of lexicographic breadth first searches [PDF]

Lexicographic Breadth First Search (LBFS) is a fundamental graph search algorithm with numerous applications, including recognition of graph classes, computation of graph parameters, and detection of certain graph structures. Rose, Tarjan and Lueker’s wellknown result on the endvertices of LBFS of chordal graphs led researchers to study LBFS endvertices of other graphs. We characterize the endvertices of LBFS of ATfree bipartite graphs. We show that deciding whether a vertex is the endvertex of an LBFS is NPcomplete for bipartite graphs but polynomiallysolvable for ATfree bipartite graphs. This is joint work with Jan Gorzny.
 SHENWEI HUANG, University of New South Wales
Linearly $\chi$Bounding $(P_6,C_4)$Free Graphs [PDF]

In this talk we show that any graph $G$ without an induced path on 6 vertices and an induced cycle on 4 vertices satisfies $\chi(G)\le \frac{3}{2}\omega(G)$, where $\chi(G)$ and $\omega(G)$ are the chromatic number and clique number of $G$, respectively. The new result unifies previous known results on the existence of linear $\chi$binding functions for several graph classes. Our proof is based on a novel structure theorem on those graphs that do not contain clique cutsets. Using this structure theorem we also design an $O(n^2m)$ time algorithm that computes a coloring with $\frac{3}{2}\omega(G)$ colors. Joint work with Serge Gaspers.
 EDWARD LEE, University of New South Wales
Fast exponentialtime algorithms via multivariate subroutines [PDF]

In this talk, we will discuss how a simple randomized algorithm, used in conjunction with multivariate subroutines, can lead to faster algorithms for subset optimization and enumeration problems. This is joint work with Serge Gaspers.
 ARASH RAFIEY, Indiana State University
Biarc Digraphs and Conservative Polymorphisms [PDF]

We introduce the class of biarc digraphs, and show they coincide with the class of digraphs
that admit a conservative semilattice polymorphism, i.e., a min ordering. This turns
out to be also the class of digraphs that admit totally symmetric conservative polymorphisms
of all arities. We give an obstruction characterization of, and a polynomial time recognition
algorithm for, this class of digraphs. The existence of a polynomial time algorithm
was an open problem due to Bagan, Durand, Filiot, and Gauwin.
We also discuss a generalization to $k$arc digraphs, which has a similar obstruction characterization.
Joint work with Pavol Hell