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
End-vertices 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 well-known result on the end-vertices of LBFS of chordal graphs led researchers to study LBFS end-vertices of other graphs. We characterize the end-vertices of LBFS of AT-free bipartite graphs. We show that deciding whether a vertex is the end-vertex of an LBFS is NP-complete for bipartite graphs but polynomially-solvable for AT-free 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 exponential-time 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
Bi-arc Digraphs and Conservative Polymorphisms  [PDF]

We introduce the class of bi-arc digraphs, and show they coincide with the class of digraphs that admit a conservative semi-lattice 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