On-line list coloring of matroids

Lason, Michael; Lubawski, Wojciech (2017). On-line list coloring of matroids. Discrete applied mathematics, 217(part 2), pp. 353-355. Elsevier 10.1016/j.dam.2016.08.002

[img] Text
1-s2.0-S0166218X16303663-main.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (364kB) | Request a copy

A coloring of a matroid is proper if elements of the same color form an independent set. A theorem of Seymour asserts that a k-colorable matroid is also colorable from any lists of size k. We prove an on-line version of this theorem. That is, a coloring from lists of size k of a k-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.

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Department of Mathematics and Statistics > Institute of Mathematics

UniBE Contributor:

Lason, Michael

Subjects:

500 Science > 510 Mathematics

ISSN:

0166-218X

Publisher:

Elsevier

Language:

English

Submitter:

Olivier Bernard Mila

Date Deposited:

17 Apr 2018 16:06

Last Modified:

23 Oct 2019 08:25

Publisher DOI:

10.1016/j.dam.2016.08.002

BORIS DOI:

10.7892/boris.109150

URI:

https://boris.unibe.ch/id/eprint/109150

Actions (login required)

Edit item Edit item
Provide Feedback