一、题目

Long cycles and spanning trees in planar graphs and beyond

二、主讲人

Guantao Chen

三、摘要

The work on finding a hamiltonian cycle in 4-connected graphs can be traced back to the early proof attempts of thefour color theorem. In 1880, Tait observed that every hamiltonian plane graph isfour face colorable. In this failed attempt, Tait made a couple of assumptions; one of them is thatevery 3-connected cubic planar graph is hamiltonian. The first counterexample was published by Tutte in 1946. On the other hand, Whitney in 1931 proved that every4-connected plane triangulationcontains a Hamiltonian cycle. Whitney's theorem has been generalized toall 4-connected planar graphs by Tutte:every 4-connected planar graph contains a hamiltonian cycle.

Tutte's result has played a central role in the development of topologic graph theory and has been generalized to projective-planar graphs, Klein bottles, toroidal graphs, and graphs embedded on other surfaces. Starting with a conjecture of Moon and Morser on circumference of a planar graph, we will address the following four topics related to the Tutte Theorem.

l Long cycles in 3-connected planar graphs;

l Long cycles in 3-connected graphs with no

-minors;

l Long cycles in 3-connected graphs with bounded degree; and

l Spanning trees without degree 2 vertices (HIST) in triangulations of surfaces and their generalizations.

四、主讲人简介

Guantao Chen, is the Regents' Professor at the Department of Mathematics and Statistics, Georgia State University. His research interests are mainly in graph theory and its applications. He works on graph structural problems in several areas, such as cycles and paths in graphs, graph coloring, and graph Ramsey theory. In recent years, most of his efforts have been in developing and understanding graph edge recoloring techniques and using them to solve some classic problems in the area. He has published more than 120 papers in major journals in combinatorics and graph theory and, with various of his collaborators, solve a number of long standing conjectures. He served as the Program Coordinator of the SIAM Discrete Mathematics Active Group (2014-2016) and a Managing Editor of the journal of Graphs and Combinatorics since 2011.

五、邀请人

颜谨 数学学院教授

六、时间

5月25日（周三）9:00-10:00

七、地点

腾讯会议

联系人：颜谨，联系方式：139 6405 5656

八、主办方

山东大学数学学院