✦ LIBER ✦

Weak Borel chromatic numbers

✍ Scribed by Stefan Geschke

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 147 KB
Volume: 57
Category: Article
ISSN: 0044-3050
DOI: 10.1002/malq.201010001

No coin nor oath required. For personal study only.

✦ Synopsis

Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G-independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge.

We show that it is consistent with an arbitrarily large size of the continuum that every closed graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ℵ1. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA.

Slightly weaker results hold for Fσ-graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable Fσ-graph has a Borel chromatic number of at most ℵ1.

We refute various reasonable generalizations of these results to hypergraphs.

📜 SIMILAR VOLUMES

Borel Chromatic Numbers

✍ A.S Kechris; S Solecki; S Todorcevic 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 342 KB

We study in this paper graph coloring problems in the context of descriptive set theory. We consider graphs G=(X, R), where the vertex set X is a standard Borel space (i.e., a complete separable metrizable space equipped with its \_-algebra of Borel sets), and the edge relation R X 2 is ``definable'

Circular Chromatic Numbers and Fractiona

Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs

✍ G.J. Chang; L. Huang; X. Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for

Mixed ramsey numbers: Chromatic numbers

Mixed ramsey numbers: Chromatic numbers versus graphs

✍ James M. Benedict; Gary Chartrand; Don R. Lick 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 399 KB

Star chromatic number

✍ A. Vince 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB

Path chromatic numbers of graphs

✍ Jin Akiyama; Hiroshi Era; Severino V. Gervacio; Mamoru Watanabe 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

Multichromatic numbers, star chromatic n

Multichromatic numbers, star chromatic numbers and Kneser graphs

✍ Johnson, A.; Holroyd, F. C.; Stahl, S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

We investigate the relation between the multichromatic number (discussed by Stahl and by Hilton, Rado and Scott) and the star chromatic number (introduced by Vince) of a graph. Denoting these by χ \* and η \* , the work of the above authors shows that χ \* (G) = η \* (G) if G is bipartite, an odd cy