On-line list coloring of matroids

DOI10.1016/J.DAM.2016.08.002MaRDI QIDQ516838zbMATH OpenOpenAlexFDO

Authors Michał Lasoń, Wojciech Lubawski

Publication date 15 March 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.2338

zbMATH Keywords

coloring gamematroidonline list coloring

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: 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. In this note we generalize this theorem to the on-line setting. We prove that a coloring of a matroid from lists of size k 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. We also prove a more general weighted version of our result with lists of varying sizes. In consequence we get a simple necessary and sufficient condition for matroid list colorability in general case. The main tool we use is the multiple basis exchange property, which we give a simple proof.

Recommendations

• List coloring of matroids and base exchange properties
• The coloring game on matroids
• Indicated coloring of matroids
• List coloring of two matroids through reduction to partition matroids
• On-line and list on-line colorings of graphs and hypergraphs

Cites work

• A note on list arboricity
• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
• An exchange theorem for bases of matroids
• Choosability and fractional chromatic numbers
• Combinatorial Nullstellensatz
• Decomposition of Finite Graphs Into Forests
• Every planar graph is 5-choosable
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 1496580 (Why is no real title available?)
• Indicated coloring of matroids
• List coloring of matroids and base exchange properties
• Minimum partition of a matroid into independent subsets
• Mr. Paint and Mrs. Correct
• Mr. Paint and Mrs. Correct go fractional
• New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs
• On-line list colouring of graphs
• The coloring game on matroids
• The game coloring number of planar graphs
• The list chromatic index of a bipartite multigraph

Cited in

(6)

• List coloring of matroids and base exchange properties
• On the toric ideal of a matroid
• Application of polynomial method to on-line list colouring of graphs
• Indicated coloring of matroids
• scientific article; zbMATH DE number 7614204 (Why is no real title available?)
• List coloring of two matroids through reduction to partition matroids

This page was built for publication: On-line list coloring of matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516838)