Coloring Problems for High-Dimensional Manifold
发布时间:2024年04月08日
浏览次数:918
发布者: Fei Tao
主讲人: Qiming Fang(BICMR)
活动时间: 从 2024-04-01 15:00 到 16:00
场地: Room 29, Quan Zhai, BICMR
Abstract:The problem of graph coloring originates from the Four Color Conjecture. After more than a century of exploration, humans have established the basic framework of graph coloring theory, found the upper bound of chromatic number for two-dimensional closed surfaces, provided a linear algorithm to determine whether a graph can be embedded in any two-dimensional closed surface, and gained preliminary understanding of the complexity of chromatic number algorithms.
Unfortunately, research on the chromatic numbers and embedding problems of graphs on manifolds is limited to two-dimensional manifolds. There is no systematic theory for the chromatic numbers and embedding problems of graphs on high-dimensional manifolds.
Starting from the coloring problem on high-dimensional manifolds, we introduce algebraic topology as a mathematical tool to establish a complete theory that combines graph coloring theory and algebraic topology, providing an upper bound of the chromatic number of high-dimensional manifolds. Based on this theory, we will provide a new algorithm for determining the upper bound of chromatic numbers for graphs, optimize the chromatic number algorithms provided by predecessors, and use this theory to study classic graph coloring problems such as the "Wegner’s Conjecture" and the "Total Coloring Conjecture".
Unfortunately, research on the chromatic numbers and embedding problems of graphs on manifolds is limited to two-dimensional manifolds. There is no systematic theory for the chromatic numbers and embedding problems of graphs on high-dimensional manifolds.
Starting from the coloring problem on high-dimensional manifolds, we introduce algebraic topology as a mathematical tool to establish a complete theory that combines graph coloring theory and algebraic topology, providing an upper bound of the chromatic number of high-dimensional manifolds. Based on this theory, we will provide a new algorithm for determining the upper bound of chromatic numbers for graphs, optimize the chromatic number algorithms provided by predecessors, and use this theory to study classic graph coloring problems such as the "Wegner’s Conjecture" and the "Total Coloring Conjecture".