✦ LIBER ✦

List multicolorings of graphs with measurable sets

✍ Scribed by A. J. W. Hilton; P. D. Johnson Jr.

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 175 KB
Volume: 54
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20201

No coin nor oath required. For personal study only.

✦ Synopsis

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 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

📜 SIMILAR VOLUMES

List colorings with measurable sets

✍ Jan Hladký; Daniel Kráal; Jean-Sébastien Sereni; Michael Stiebitz 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

## 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 an

Extending the disjoint-representatives t

Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs

✍ Cropper, M. M.; Goldwasser, J. L.; Hilton, A. J. W.; Hoffman, D. G.; Johnson, P. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 333 KB

Philip Hall's famous theorem on systems of distinct representatives and its not-so-famous improvement by Halmos and Vaughan (1950) can be regarded as statements about the existence of proper list-colorings or listmulticolorings of complete graphs. The necessary and sufficient condition for a proper

The orders of graphs with prescribed deg

The orders of graphs with prescribed degree sets

✍ Timothy A. Sipka 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB 👁 1 views

## Abstract The degree set 𝒟^G^ of a graph __G__ is the set of degrees of the vertices of __G.__ For a finite nonempty set __S__ of positive integers, all positive integers __p__ are determined for which there exists a graph __G__ of order __p__ such that 𝒟^G^ = __S__.

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)

Graphs with given odd sets and the least

Graphs with given odd sets and the least number of vertices

✍ Louis Hakimi, S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 2 views

This note presents a solution to the following problem posed by Chen, Schelp, and Soltés: find a simple graph with the least number of vertices for which only the degrees of the vertices that appear an odd number of times are given.

Circular Chromatic Numbers of Distance G

Circular Chromatic Numbers of Distance Graphs with Distance Sets Missing Multiples

✍ Lingling Huang; Gerard J Chang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 114 KB

Given positive integers m, k, s with m > sk, let D m,k,s represent the set {1, 2, . . . , m}\{k, 2k, . . . , sk}. The distance graph G(Z , D m,k,s ) has as vertex set all integers Z and edges connecting i and j whenever |i -j| ∈ D m,k,s . This paper investigates chromatic numbers and circular chroma