PIMS-UVic Discrete Math Seminar: Anton Bernshteyn

The line graph of a graph $G$ is the graph $L$ with vertex set $E(G)$ in which two vertices are adjacent if and only if the corresponding edges of $G$ share an endpoint. A famous theorem of Beineke characterizes the class of line graphs by a list of 9 forbidden induced subgraphs. In this talk we will be interested in the following question: Given an "explicit description" of a line graph $L$, when does the underlying graph $G$ also have an "explicit description"? To use the precise terminology (which I will define in the talk), when is a Borel graph $L$ a line graph of a Borel graph $G$? It turns out that to answer this question, we need to expand Beineke's list to include a tenth forbidden subgraph. This is joint work with James Anderson.