  français conference home canadam home

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

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.

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.