Publication details
List Colorings with Measurable Sets
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Graph Theory |
| Citation | |
| Doi | http://dx.doi.org/10.1002/jgt.20335 |
| Keywords | fractional chromatic number; Hall's theorem; list coloring; measurable sets |
| Description | 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) subset of L(v) such that each c(v) has measure one and c(v) boolean AND c(v') = phi 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. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 59: 229-238, 2008 |