On-line list coloring of matroids

详细信息    查看全文

• 作者：Michał Lasoń^a ; ^b ; ^{michalason@gmail.com} ; Wojciech Lubawski^b ; ^{w.lubawski@gmail.com}
• 关键词：Matroid ; On-line list coloring ; Coloring game
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：353-355
• 全文大小：355 K
• 卷排序：217

文摘

A coloring of a matroid is proper   if elements of the same color form an independent set. A theorem of Seymour asserts that a kk-colorable matroid is also colorable from any lists of size kk.We prove an on-line version of this theorem. That is, a coloring from lists of size kk of a kk-colorable matroid is possible, even if appearances of colors in the lists are recovered color by color by an adversary, while our job is to assign a color immediately after it is recovered.