Premium
List multicolorings of graphs with measurable sets
Author(s) -
Hilton A. J. W.,
Johnson P. D.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20201
Subject(s) - mathematics , disjoint sets , combinatorics , generalization , colored , discrete mathematics , graph , mathematical analysis , materials science , composite material
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 from an arbitrary atomless, semifinite measure space, and the color sets are to have prescribed measures rather than prescribed cardinalities. We adapt a proof technique of Bollobás and Varopoulos to prove an analog of one of the major theorems about ordinary list multicolorings, a generalization and extension of Hall's marriage theorem, due to Cropper, Gyárfás, and Lehel. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 179–193, 2007