CanaDAM 2019
SFU Harbour Centre, May 29 - 31, 2019

Extremal graph theory
Chair: Felix Lazebnik (University of Delaware)

ANDRZEJ CZYGRINOW, Arizona State University
Rainbow cycles in colored graphs  [PDF]

For a vertex $v$ in a graph $G$ let $d^c(v)$ denote the number of distinct colors used on the edges incident to $v$, and let $\delta^c(G)$ denote the minimum of $d^c(v)$. We will give tight conditions for $\delta^c(G)$ which guarantee existence of even and odd rainbow cycles of any fixed length in $G$. This is a joint work with T. Molla, B. Nagle, and R. Oursler.

RACHEL KIRSCH, London School of Economics
Many cliques with few edges  [PDF]

The problem of maximizing the number of cliques has been studied within several classes of graphs. For example, among graphs on $n$ vertices with clique number at most $r$, the Tur\'an graph $T_r(n)$ maximizes the number of copies of $K_t$ for each size $t$. Among graphs on $m$ edges, the colex graph $\mathcal{C}(m)$ maximizes the number of $K_t$'s for each size $t$.

In recent years, much progress has been made on the problem of maximizing the number of cliques among graphs with $n$ vertices and maximum degree at most $r$. In this talk, we discuss the edge analogue of this problem: which graphs with $m$ edges and maximum degree at most $r$ have the maximum number of cliques? We prove in some cases that the extremal graphs contain as many disjoint copies of $K_{r+1}$ as can fit, with the leftovers in another component. These remaining edges form a colex graph.

YOUNGHO YOO, Georgia Institute of Technology
The extremal functions for triangle-free graphs with excluded minors  [PDF]

Linklessly embeddable graphs are 3-dimensional analogues of planar graphs which include apex planar graphs. While there is no known analogue of Euler's formula for linkless embeddings, a tight bound of $4n-10$ on the number of edges in linklessly embeddable graphs can be obtained from their excluded minor characterization and a theorem of Mader on the extremal functions for graphs with no $K_p$ minor for small $p$. We prove an analogue of Mader's theorem for triangle-free graphs, and also show that apex planar graphs satisfy the edge bound of $3n-9+\frac{t}{3}$, where $t$ is the number of triangles. This bound is conjectured to hold for all linklessly embeddable graphs. Joint work with Robin Thomas.