BARC double talk by Mohar and Kawarabayashi

BARC is pleased to host two esteemed graph theorists at DIKU and invites everyone to join our double talk on Monday September 16, 2024, followed by a lunch reception on site.

Bojan Mohar, Professor at the Department of Mathematics at the Simon Fraser University, Canada, and at Ljubljana University, Slovenia, will give his talk at 10:01 on "Random embeddings of graphs in surfaces":

Abstract:
3-connected planar graphs have (essentially) unique embedding in the plane. This fact is a basis of many other results, in particular of the area known as "graph drawing" and serves as a cornerstone in the theory of algorithms on planar graphs. However such a graph has many combinatorially nonequivalent embeddings in the torus or in surfaces of even higher genus. Counting how many such embeddings are there has applications not only in mathematics but also in theoretical physics and theoretical computer science. The speaker will discuss some of the fundamental results about random 2-cell embeddings of graphs in surfaces.

Bio:
Bojan Mohar is a Canadian and Slovenian graph theorist, whose main interest lies in algebraic, topological and structural graph theory. He published well over 300 research papers. Jointly with Carsten Thomassen, he wrote a book about graphs on surfaces that became the main reference in this area. He is a Fellow of the AMS, SIAM, and CMS, and a Fellow of the Royal Society of Canada and the Engineering Academy of Slovenia. In 2016 he got Euler Medal by ICA; in 2018 he was awarded the John Synge Award by the Royal Society for his work in topological graph theory.

Ken-ichi Kawarabayashi, Professor at the National Institute of Informatics, Japan, will give his talk at 11:15 on "Three-edge-coloring (Tait coloring) projective planar cubic graphs: A generalization of the Four Color Theorem":

Abstract:
We p/rove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In other words, the only (non-trivial) snark that can be embedded in the projective plane is the Petersen graph. This implies that a 2-connected cubic (multi)graph that can be embedded in the projective plane is not 3-edge-colorable if and only if it can be obtained from the Petersen graph by replacing each vertex by a 2-edge-connected planar cubic (multi)graph. Here, a replacement of a vertex v in a cubic graph G is the operation that takes a 2-connected planar (cubic) multigraph H containing some vertex u of degree 3, unifying G− v and H − u, and connecting the vertices in NG[v] in G− v with the three neighbors of u in H − u with 3 edges. Any graph obtained in such a way is said to be Petersen-like. This result is a nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability. To appear in FOCS'24.

Bio:
Ken-ichi Kawarabayashi has been a professor at the National Institute of Informatics since 2009 and became a professor at the University of Tokyo in 2022. From 2019 to 2021, he also served as the deputy director general of the National Institute of Informatics. His research interests include graph theory, combinatorics, scalable algorithms, combinatorial optimization, and their application to machine learning, as well as the theoretical analysis of deep learning. In addition to his academic roles, Ken-ichi serves as an editor for Algorithmica, Journal of Graph Theory, Graphs and Combinatorics, TheoriTCS, and four other prestigious journals. He has been recognized with SODA'13 best paper award, Japan Academy medal in 2013, and the Fulkerson Prize in 2021 for his contributions to the field.

Both guest are hosted by Mikkel Thorup, Professor at DIKU and PI of BARC and after the talks we invite all participants to join for a lunch reception with ample opportunity to mingle with colleagues from both Mathematics as well at Computer Science.