every 5-connected nonplanar graph contains a subdivision of $K_5$. This
conjecture was proved by Ma and Yu for graphs containing $K_4^-$. Recently,
we proved this entire Kelmans-Seymour conjecture. In this talk, I will give
a sketch of our proof, and discuss related problems.
This is joint work with Dawei He and Xingxing Yu.
Joint work with Shachar Lovett.
having maximum total degree two. We explore a number of questions
regarding genome rearrangement, a common mode of molecular evolution. In
the single cut-or-join model for genome rearrangement, a genome can
mutate in one of two ways at any given time: a cut divides a degree two
vertex into two degree one vertices while a join merges two degree one
vertices into one degree two vertex.
Fix a set of genomes, each having the same set of edge labels. The
number of ways for one genome to mutate into another can be computed in
polynomial time. The number of medians can also be computed in
polynomial time. While single cut-or-join is, computationally, the
simplest mathematical model for genome rearrangement, determining the
number of most parsimonious median scenarios remains #P-complete. We
will discuss these and other complexity results that arose from an
abstraction of this problem. [This is joint work with Istvan Miklos.]