Georgia Institute of Technology School of Mathematics | Georgia Institute of Technology | Atlanta, GA

Given a multigraph $G=(V,E)$, the chromatic index $\chi'(G)$ is the minimum number of colors needed to color the edges of $G$ such that no two incident edges receive the same color. Let $\Delta(G)$ be the maximum degree of $G$ and let  $\Gamma(G):=\max \big\{\frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hskip 2mm
{\rm and \hskip 2mm odd} \big\}$. $\Gamma(G)$ is called the density of $G$. Clearly, the density is a lower bound for the chromatic index $\chi'(G)$. Moreover, this value can be computed in polynomial time. Goldberg and Seymour in the 1970s conjectured that $\chi'(G)=\lceil\Gamma(G)\rceil$ for any multigraph $G$ with $\chi'(G)\geq\Delta(G)+2$, known as the Goldberg-Seymour conjecture. In this talk we will discuss this conjecture and some related open problems. This is joint work with Guantao Chen and Wenan Zang.

In this talk we’ll discuss strong 4-colourings of graphs and prove two new cases of the Strong Colouring Conjecture. Let H be a graph with maximum degree at most 2, and let G be obtained from H by gluing in vertex-disjoint copies of K_4. We’ll show that if H contains at most one odd cycle of length exceeding 3, or if H contains at most 3 triangles, then G is 4-colourable. This is joint work with Greg Puleo.

For a planar graph $H$, let ${\bf N}_{\mathcal P}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. The case where $H$ is the path on $3$ vertices, $H=P_3$, was established by Alon and Caro. The case of $H=P_4$ was determined, also exactly, by Gy\H{o}ri, Paulos, Salia, Tompkins, and Zamora. In this talk, we will give the asymptotic values for $H$ equal to $P_5$ and $P_7$ as well as the cycles $C_6$, $C_8$, $C_{10}$ and $C_{12}$ and discuss the general approach which can be used to compute the asymptotic value for many other graphs $H$. This is joint work with Debarun Ghosh, Ervin Győri, Addisu Paulos, Nika Salia, Chuanqi Xiao, and Oscar Zamora and also joint work with Chris Cox.

Let $G$ be a connected finite graph. Backman, Baker, and Yuen have constructed a family of explicit and easy-to-describe bijections $g_{\sigma,\sigma^*}$ between spanning trees of $G$ and $(\sigma,\sigma^*)$-compatible orientations, where the $(\sigma,\sigma^*)$-compatible orientations are the representatives of equivalence classes of orientations up to cycle-cocycle reversal which are determined by a cycle signature $\sigma$ and a cocycle signature $\sigma^*$. Their proof makes use of zonotopal subdivisions and the bijections $g_{\sigma,\sigma^*}$ are called geometric bijections. Recently we have extended the geometric bijections to  subgraph-orientation correspondences. In this talk, I will introduce the bijections and the geometry behind them.