A Caltech Library Service

Borel Chromatic Numbers

Kechris, A. S. and Solecki, S. and Todorcevic, S. (1999) Borel Chromatic Numbers. Advances in Mathematics, 141 (1). pp. 1-44. ISSN 0001-8708. doi:10.1006/aima.1998.1771.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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", i.e., Borel, analytic, co-analytic, etc. A Borel n-coloring of such a graph, where 1⩽ n ⩽ N_0 , is a Borel map c: X → Y with card(Y)=n, such that xRy⇒c(x) ≠ {c( y). If such a Borel coloring exists we define the Borel chromatic number of G, in symbols X_B(G), to be the smallest such n. Otherwise we say that G has uncountable Borel chromatic number, in symbols X_B(G) > N_0.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1999 by Academic Press. Received November 16, 1996; accepted April 30, 1998. The author acknowledges the support of the Mathematics Department at Caltech during his visits in January 1992 and 1995, the NSERC of Canada, and the Science Foundation of Serbia. Research partially supported by NSF Grant DMS-9317509. We thank A. Ditzen for allowing us to include the joint result 1.1 and A. Louveau for 8.2.
Funding AgencyGrant Number
Caltech Mathematics DepartmentUNSPECIFIED
Science Foundation of SerbiaUNSPECIFIED
Issue or Number:1
Record Number:CaltechAUTHORS:20130517-100529842
Persistent URL:
Official Citation:A.S Kechris, S Solecki, S Todorcevic, Borel Chromatic Numbers, Advances in Mathematics, Volume 141, Issue 1, 15 January 1999, Pages 1-44, ISSN 0001-8708, 10.1006/aima.1998.1771. (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:38554
Deposited By: Ruth Sustaita
Deposited On:22 May 2013 17:01
Last Modified:09 Nov 2021 23:38

Repository Staff Only: item control page