Coloring Problems for High-Dimensional Manifold
Time: 2024-04-08
Published By: Fei Tao
Speaker(s): Qiming Fang(BICMR)
Time: 15:00-16:00 April 1, 2024
Venue: 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".