𝔖 Bobbio Scriptorium
✦   LIBER   ✦

List colorings with measurable sets

✍ Scribed by Jan Hladký; Daniel Kráal; Jean-Sébastien Sereni; Michael Stiebitz

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
140 KB
Volume
59
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The measurable list chromatic number of a graph G is the smallest number ξ such that if each vertex v of G is assigned a set L(v) of measure ξ in a fixed atomless measure space, then there exist sets $c(v)\subseteq L(v)$ such that each c(v) has measure one and $c(v)\cap c(v') = \emptyset$ for every pair of adjacent vertices v and v'. We provide a simpler proof of a measurable generalization of Hall's theorem due to Hilton and Johnson [J Graph Theory 54 (2007), 179–193] and show that the measurable list chromatic number of a finite graph G is equal to its fractional chromatic number. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 229–238, 2008

📜 SIMILAR VOLUMES

List multicolorings of graphs with measu
List multicolorings of graphs with measurable sets
✍ A. J. W. Hilton; P. D. Johnson Jr. 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB

## Abstract In an ordinary list multicoloring of a graph, the vertices are “colored” with subsets of pre‐assigned finite sets (called “lists”) in such a way that adjacent vertices are colored with disjoint sets. Here we consider the analog of such colorings in which the lists are measurable sets fr

List Colorings of K5-Minor-Free Graphs W
List Colorings of K5-Minor-Free Graphs With Special List Assignments
✍ Daniel W. Cranston; Anja Pruchnewski; Zsolt Tuza; Margit Voigt 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

The following question was raised by Bruce Richter. Let G be a planar, 3-connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L-list colorable for every list assignment L with |L(v)|=min{d(v), 6} for all v ∈ V (G)? More generally, we ask for which pairs (r, k)

Coloring graphs from lists with bounded
Coloring graphs from lists with bounded size of their union
✍ Daniel Král'; Jiří Sgall 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract A graph __G__ is __k‐choosable__ if its vertices can be colored from any lists __L__(ν) of colors with |__L__(ν)| ≥ __k__ for all ν ∈ __V__(__G__). A graph __G__ is said to be (__k,ℓ__)‐__choosable__ if its vertices can be colored from any lists __L__(ν) with |__L__(ν)| ≥__k__, for all

Very rapidly mixing Markov chains for 2Δ
Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4
✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A

The Inversion of NMR Log Data Sets with
The Inversion of NMR Log Data Sets with Different Measurement Errors
✍ Keh-Jim Dunn; Gerald A. LaTorraca 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 353 KB

We present a composite-data processing method which simultaneously processes two or more data sets with different measurement errors. We examine the role of the noise level of the data in the singular value decomposition inversion process, the criteria for a proper cutoff, and its effect on the unce