学术报告(操宜新 9.14)

离散数学学术报告--Local Coloring and its Complexity

发布人:周妍 发布日期:2018-09-06
主题
离散数学学术报告--Local Coloring and its Complexity
活动时间
-
活动地址
数学楼416讲学厅
主讲人
操宜新 助理教授(香港理工大学)

摘要:

A $k$-coloring of a graph is an assignment of integers between $1$ and $k$ to vertices in the graph such that the endpoints of each edge receive different numbers.  We study a local variation of the coloring problem, which imposes further requirements on three vertices: We are not allowed to use two consecutive numbers for a path on three vertices, or three consecutive numbers for a cycle on three vertices.  Given a graph $G$ and a positive integer $k$, the local coloring problem asks for whether $G$ admits a local $k$-coloring.  We give a characterization of graphs admitting local $3$-coloring, which implies a simple polynomial-time algorithm for it.  Li et al.~[\href{http://dx.doi.org/10.1016/j.ipl.2017.09.013} {Inf.~Proc.~Letters 130 (2018)}] recently showed it is NP-hard when $k$ is an odd number of at least $5$, or $k = 4$.  We show that it is NP-hard when $k$ is even and $k > 4$, thereby completing the complexity picture of this problem.

 

数学学院

2018年9月6日