CanaDAM 2015
University of Saskatchewan, June 1 - 4, 2015

Graph packings and colorings
Organizer and Chair: Daniel Kral (University of Warwick) and Bojan Mohar (Simon Fraser University)

ROSS CHURCHLEY, Simon Fraser University
Packing odd edge-disjoint $(u,v)$-trails  [PDF]

Menger's theorem gives a famous duality between packings and coverings of $(u,v)$-paths in a graph. But perfect duality may not exist if the paths are further restricted: for example, the maximum number of edge-disjoint odd $(u,v)$-paths may be less than the number of edges it takes to cover all such paths. In this talk, we explain an approximate duality for packings of odd trails: if a graph does not have $k$ edge-disjoint odd $(u,v)$-trails, it has a set of fewer than $8k$ edges intersecting all such trails.

This is joint work with Bojan Mohar and Hehui Wu.

PING HU, University of Warwick
Rainbow triangles in three-colored graphs  [PDF]

Erd\H os and S\'os proposed a problem of determining the maximum number $F(n)$ of rainbow triangles in 3-edge-colored complete graphs on $n$ vertices. They conjectured that $F(n)=F(a)+F(b)+F(c)+F(d)+abc+abd+acd+bcd$, where $a+b+c+d=n$ and $a,b,c,d$ are as equal as possible. We prove that the conjectured recurrence holds for sufficiently large $n$. We also prove the conjecture for $n = 4^k$ for all $k \geq 0$. These results imply that $\lim F(n)/{n\choose 3}=0.4$, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.

Joint work with József Balogh, Bernard Lidický, Florian Pfender, Jan Volec and Michael Young.

ROSS KANG, Radboud University Nijmegen
Partition of random graphs into subgraphs of bounded component order  [PDF]

We consider vertex partitions of the binomial random graph $G_{n,p}$. For $np\to\infty$, we observe the following phenomenon: for any partition into asymptotically fewer than $\chi(G_{n,p})$ parts, i.e. $o(np/\log np)$ parts, there must be one part whose induced subgraph has a connected component of order at least roughly the average part size. For $0 < p <1$ fixed, we obtain more precise information: in particular, we find something subtle happens at the threshold $t = \Theta(\log n)$, and we determine the asymptotic first-order behaviour.

This is joint work with Nicolas Broutin (INRIA Rocquencourt).

ROBERT SAMAL, Charles University
Unique Vector Coloring and Cores  [PDF]

Strict vector coloring is one formulation of an optimization program for Lovasz theta function: assign vectors to vertices so that adjacent vertices obtain vectors with large angle in-between. We study when this assignment is unique by using geometric rigidity theory. We then show how to use this notion as a tool to prove a graph is a core. We successfully apply this to several instances of strongly regular graphs.

HEHUI WU, University of Olemiss
Triangle-free subgraph with large fractional chromatic number  [PDF]

It is well known that for any $k$ and $g$, there is a graph with chromatic number at least $k$ and girth at least $g$. In 1970's, Erd\H{o}s and Hajnal conjectured that for any numbers $k$ and $g$, there exists a number $f(k, g)$, such that for any graph with chromatic number at least $f(k, g)$, it contains a subgraph with chromatic number at least $k$ and girth at least $g$. In 1978, R\"{o}dl proved the case for $g=4$ and arbitrary $k$. We prove the fractional chromatic number version of R\"{o}dl's result.

This is joint work with Bojan Mohar.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Saskatchewan