CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Graph Theory II

RUSSELL CAMPBELL, University of Victoria
Reflexive Injective Oriented Colouring  [PDF]

We focus on said colourings that are neighbourhood-injective, which we call rio-colourings. The question of whether an oriented graph is $k$-rio-colourable turns out to hold dichotomy above and below $k$=3 and we briefly consider an interesting structure that resulted from its proof. We characterize the $2$-rio-colourable oriented graphs, and finish by presenting rio-cliques along with bounds on the rio-chromatic number, which can be improved when restricting ourselves to oriented trees.

ANDRZEJ CZYGRINOW, Arizona State University
Tiling in Bipartite Graphs  [PDF]

Bipartite graph tiling was studied by Zhao who gave the minimum degree conditions for a balanced bipartite graph on $2ms$ vertices to contain $m$ vertex disjoint copies of $K_{s,s}$. The case $s<t$ was recently solved by Hladky, Schacht and Czygrinow, DeBiasio. In this talk we will discuss the minimum degree conditions for the existence of a bipartite tiling and a sum of degree condition for the same problem. This is a joint work with DeBiasio.

ANDREW D. KING, Columbia University
Proving the Lovász-Plummer Conjecture  [PDF]

In the 1970s, Lovász and Plummer conjectured that every cubic bridgeless graph has exponentially many perfect matchings. This was proven by Voorhoeve for bipartite graphs and by Chudnovsky and Seymour for planar graphs. In this talk I will describe our proof of the general case, which uses elements of both aforementioned partial results as well as Edmonds' characterization of the perfect matching polytope.

(Joint work with Louis Esperet, František Kardoš, Daniel Král', and Sergey Norin.)

HENRY MARTYN MULDER, Econometric Institute, Erasmus Universiteit, Rotterdam
Axiomatic characterization of location functions  [PDF]

Since Kenneth Arrow’s ground-breaking work on consensus in 1951 this has been a major area in mathematical economics: how to reach consensus in a rational way. This is modeled by a consensus function that satisfies certain natural and intuitively pleasing axioms. We survey recent and new results on a special type of consensus: finding an optimal location, such as the center, the median, and the mean.

ASIYEH SANAEI, Memorial University of Newfoundland
Constructions of 3-existentially closed graphs using graph operations  [PDF]

A graph is $n$-existentially closed ($n$-e.c.) if for any two sets $A,B\subset V$ with $|A|+|B|=n$ there exists a vertex $x\in V\setminus(A\cup B)$ that is adjacent to every vertex in $A$ and to none in $B$. We produce a large family of $3$-e.c. graphs by considering a binary graph operation (denoted by $\bowtie$) and determining necessary and sufficient conditions for $G\bowtie H$ to be $3$-e.c. if $H$ is $3$-e.c.

Joint work with David Pike.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria