报告题目:Majority Paintability
报告人:Grzegorz Gutowski,雅盖隆大学副教授
报告时间:2023年5月10日15:00-16:00
报告地点:21-427
摘要:
A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors.
In this talk we simplify some proof techniques and generalize previously known results on various variants of majority coloring.
In particular, our unified and simple approach gives the best known results for:
• directed and undirected graphs,
• (1/k)-majority colorings (each vertex has the same color as at most 1/k of its out-neighbors),
• weighted edges,
• list colorings (choosability),
• on-line list colorings (paintability),
• non-uniform list lengths,
• ranked colors.
邀请人:朱绪鼎