CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Partitioning Graphs into Independent Sets and Cliques
Organizer and Chair: Dennis D.A. Epple (University of Victoria)

TINAZ EKIM, Bogazici University
Defective Cocolorings  [PDF] [SLIDES]

Given a graph $G$ and an integer $k$, a set $S$ of vertices in $G$ is $k$-sparse if $G[S]$ has degree at most $k$. Also, a set $D$ of vertices is $k$-dense if $D$ is $k$-sparse in $\bar G$. We first consider the defective Ramsey numbers. Then, we study the defective cocoloring problem which consists in partitioning the vertex set of a given graph into $k$-sparse and $k$-dense sets. Let $c_k(m)$ be the largest number $n$ such that all $n$-graphs are $k$-defectively cocolorable by at most $m$ colors. We compute some new values for $c_k(m)$ by efficient graph generation methods.

DENNIS D.A. EPPLE, University of Victoria
Young diagrams for $(k,l)$-colourings  [PDF]

A $(k,l)$-colouring of a graph $G$ is a partition of its vertex set into $k$ independent sets and $l$ cliques (empty sets are allowed). We define the \emph{colouring diagram} of $G$ to be the Young diagram of all pairs $(k,l)$, such that $G$ is not $(k,l)$-colourable. In this talk we present some characterizations for graphs with a given colouring diagram, as well as investigate connections between the colouring diagram and other graph parameters.

PAVOL HELL, Simon Fraser University
Matrix partitions  [PDF]

Matrix partitions are partitions into independent sets, cliques, and unrestricted sets, with connections between these sets also possibly restricted in a similar way, encoded by a matrix. I will describe new results on matrix partitions for graphs and digraphs, reporting on joint work with Dennis Epple, Oren Shklarsky, Tomas Feder, and Cesar Hernandez Cruz.

Counting Partitions of Graphs  [PDF] [SLIDES]

We study the complexity of counting graph partitions described by a symmetric $\{0,1,*\}$-matrix $M$ which generalize graph colourings and homomorphisms. The complexity of counting graph homomorphisms have been previously classified, and most turned out to be $\#$P-complete, with only trivial exceptions. By contrast, we exhibit $M$-partition problems with interesting non-trivial counting algorithms. We classify the complexity of counting $M$-partitions for all matrices $M$ of size less than four. Among matrices not accounted for by the existing results on counting homomorphisms, all matrices which do not contain the matrices for independent sets or cliques yield tractable counting problems.

JURAJ STACHO, University of Warwick
Stable-$\Pi$ partitions of graphs  [PDF] [SLIDES]

For a set of graphs $\Pi$, the STABLE-$\Pi$ problem asks whether a given graph $G$ has an independent set $S$ such that $G-S\in \Pi$. We systematically study the STABLE-$\Pi$ problem with respect to the speed (a term meaning size) of $\Pi$. We show that for all hereditary classes $\Pi$ with a subfactorial speed of growth, STABLE-$\Pi$ is solvable in polynomial time. We then study factorial hereditary classes. We show that, contrary to a conjecture proposed in the literature, the complexity of STABLE-$\Pi$ is polynomial for nearly all minimal factorial hereditary classes $\Pi$.

Joint work with Konrad Dabrowski and Vadim Lozin.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland