报告时间：2018-04-23 16:30
报告地点：数理化楼A210教室
报告人：朱绪鼎
主办单位：数学学院
报告人简介：
朱绪鼎，浙江师范大学特聘教授，离散数学研究中心主任。全职到浙江师范大学任教。1991年获加拿大卡尔加里大学数学博士。曾任台湾中山大学西湾讲座教授，台湾科学委员会数学学门审议委员、谘议委员，台湾数学会学术委员会委员。获得台湾科学委员会杰出研究奖，台湾数学学会学术奖，主持台湾杰出学者研究计划。研究专长是图论、演算法和组合优化。在SCI期刊发表论文200余篇。依MathSciNet统计，所发表论文被引用2100余次。H-index为23。现任《Electronic J. Combinatorics》, 《J. Graph Theory》, 《European J. Combin.》，《Discrete. Mathematics》，《Contrib.
Discrete Math.》, 《Discuss. Math. Graph Theory Graph Theory》, 《Bulletin of Academia Sinica》, 《Taiwanese Journal of Mathematics》等国际学术期刊编委。
报告简介：
Given a graph G and a mapping f : V(G) to {1,2,...}, an f-painting game on G is played by two players: Lister and Painter. Initially, each vertex v is uncoloured and is given f(v) tokens. In each round, Lister selects a set M of uncoloured vertices, and removes one token from each chosen vertex. Painter colours a subset X of M. The colouring is required to be legal. Usually, legal means that X is an independent set of G, i.e., no two adjacent vertices are coloured the same colour. In a d-defective f-painting game, legal means that G[X] induces a graph of maximum degree at most d. If at the end of some round, there is an uncoloured vertex with no more token left, then Lister wins the game. Otherwise, at the end of some round, all vertices are coloured. Then Painter wins the game. We say G is f-paintable if Painter has a winning strategy in this game. We say G is k-paintable if G is f-paintable with f(v) = k for every vertex v. This game is the online version list colouring of graphs. The online choice number (also called the painter number) of G is the minimum k such that G is k-paintable. It follows from the definition that for any graph G, the online choice number is equal to or greater than the choice number of G. In this talk, I shall survey research on the study of online list colouring of graphs.
