Graph packings and colorings
Responsable et prÃ©sident:
Daniel Kral (University of Warwick) et
Bojan Mohar (Simon Fraser University)
[
PDF]
 ROSS CHURCHLEY, Simon Fraser University
Packing odd edgedisjoint $(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 edgedisjoint 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$ edgedisjoint 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 threecolored graphs [PDF]

Erd\H os and S\'os proposed a problem of determining the maximum number $F(n)$ of rainbow
triangles in 3edgecolored 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 firstorder 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 inbetween. 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
Trianglefree 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.