报告题目1：Local Computation Algorithms for Hypergraph Coloring
报告人：Jakub Kozik（Jagiellonian University)
报告时间：2024年5月8日（周三）14:30-17:30
报告地点：20-200
报告摘要：The model of Local Computation Algorithms (LCA) is intended to capture a situation where some computation has to be performed on a large instance but, at any specific time, only parts of the answer are required. The interaction with a local computation algorithm is organized in the sequence of queries about fragments of a global solution. The algorithm shall answer each consecutive query in sublinear time (wrt the size of the instance), systematically producing a partial answer that is consistent with some global solution. We are going to discuss local constraints that enable designing such algorithms for the problems of hypergraph coloring.
报告人简介：Jakub Kozik obtained his PhD degree in computer science at the Jagiellonian University in Krakow in 2006. Since then, he has been working at the Jagiellonian University where he currently holds a position of a professor at the Department of Mathematics and Computer Science. His initial research topics can be placed at the intersection of logic and analytic combinatorics. Later, his scientific interests shifted to extremal combinatorics and probabilistic algorithms.
报告题目2：First-Fit Coloring of Forests in Random Arrival Model
报告人：Grzegorz Gutowski (Jagiellonian University)
报告时间：2024年5月8日（周三）14:30-17:30
报告地点：20-200
报告摘要：We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses at most O(log n / log log n) colors in expectation to color any forest with n vertices, and that this bound is best possible.
报告人简介：Grzegorz Gutowski obtained his PhD degree in computer science at the Jafiellonian University in Kraków in 2012. His main research interests are in graph theory, with focus on algorithms for colorings, drawings, and representations of graphs.
报告题目3：The Odd Coloring
报告人：Riste Škrekovski (University of Ljubljana)
报告时间：2024年5月8日（周三）14:30-17:30
报告地点：20-200
报告摘要：A proper vertex coloring φ of graph G is said to be odd if for each non-isolated vertex x ∈ V (G) there exists a color c such that φ−1(c) ∩ N(x) is odd-sized, i.e. in the neighborhood of each vertex some color appears odd number of times. The minimum number of colors in any odd coloring of G, denoted χo(G), is the odd chromatic number. Odd colorings were recently introduced in [M. Petruševski, R. Škrekovski: Colorings with neighborhood parity condition, Discret. Appl. Math. 321 385-391 (2022)].
In the talk we discuss various basic properties of this new graph parameter, establish several upper bounds, several characterizations, and pose some questions and problems. We will also consider another new and related coloring, so called the proper conflict-free coloring.
This is a joint work with Mirko Petruševski from Skopje, Macedonia & Yair Caro from Haifa, Israel.
报告人简介：Riste Škrekovski obtained his PhD degree in graph colorings at the University of Ljubljana in 2000 and continued his postdoctoral education at Charles University, Prague, Czech Republicand， Simon Fraser University, Burnaby, Canada. Nowadays, he works in University of Ljubljana and is one of the leading researchers at Faculty of Information Studies of Novomesto, Slovenia. His main research interests are various topics in classical graph theory, but he is also interested in applied and interdisciplinary areas as chemical mathematics, complex networks, the arts and mathematics.