Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Semialgebraic graphs having countable list-chromatic numbers

Author: James H. Schmerl
Journal: Proc. Amer. Math. Soc. 144 (2016), 1429-1438
MSC (2010): Primary 05C15, 05C63
Published electronically: July 30, 2015
MathSciNet review: 3451221
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For $ n \geq 1$ and a countable, nonempty set $ D$ of positive reals, the $ D$-distance graph $ {\bf X}_n(D)$ is the graph on Euclidean $ n$-space $ \mathbb{R}^n$ in which two points form an edge exactly when the distance between them is in $ D$. Each of these graphs is $ \sigma $-algebraic. Komjáth characterized those $ {\bf X}_n(D)$ having a countable list-chromatic number, easily implying a different, but essentially equivalent, noncontainment characterization. It is proved here that this noncontainment characterization extends to all $ \sigma $-algebraic graphs. We obtain, in addition, similar noncontainment characterizations for those $ \sigma $-semialgebraic graphs and those semialgebraic graphs having countable list-chromatic numbers.

References [Enhancements On Off] (What's this?)

  • [1] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), no. 2, 125-134. MR 1179249 (93h:05067),
  • [2] P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar 17 (1966), 61-99. MR 0193025 (33 #1247)
  • [3] András Hajnal and Péter Komjáth, What must and what need not be contained in a graph of uncountable chromatic number?, Combinatorica 4 (1984), no. 1, 47-52. MR 739412 (85d:05115),
  • [4] Tommy R. Jensen and Bjarne Toft, Choosability versus chromaticity--the plane unit distance graph has a $ 2$-chromatic subgraph of infinite list-chromatic number, Appendix 1 by Leonid S. Melnikov and Vadim G. Vizing and Appendix 2 by Noga Alon, Geombinatorics 5 (1995), no. 2, 45-64. MR 1352332 (96i:05066)
  • [5] Tommy R. Jensen and Bjarne Toft, Graph coloring problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1304254 (95h:05067)
  • [6] Peter D. Johnson Jr., The choice number of the plane, Geombinatorics 3 (1994), no. 4, 122-128. MR 1268721 (95a:05038)
  • [7] Péter Komjáth, A decomposition theorem for $ {\bf R}^n$, Proc. Amer. Math. Soc. 120 (1994), no. 3, 921-927. MR 1169038 (94h:04005),
  • [8] Péter Komjáth, The list-chromatic number of infinite graphs defined on Euclidean spaces, Discrete Comput. Geom. 45 (2011), no. 3, 497-502. MR 2770548 (2012e:05139),
  • [9] Péter Komjáth, The list-chromatic number of infinite graphs, Israel J. Math. 196 (2013), no. 1, 67-94. MR 3096584,
  • [10] James H. Schmerl, The list-chromatic number of Euclidean space, Geombinatorics 5 (1995), no. 2, 65-68. MR 1352333 (96h:05078)
  • [11] James H. Schmerl, A generalization of Sierpiński's paradoxical decompositions: coloring semialgebraic grids, J. Symbolic Logic 77 (2012), no. 4, 1165-1183. MR 3051619,
  • [12] Alexander Soifer, The mathematical coloring book, Mathematics of coloring and the colorful life of its creators; With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau, Springer, New York, 2009. MR 2458293 (2010a:05005)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C15, 05C63

Retrieve articles in all journals with MSC (2010): 05C15, 05C63

Additional Information

James H. Schmerl
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269

Received by editor(s): May 27, 2014
Received by editor(s) in revised form: April 13, 2015
Published electronically: July 30, 2015
Communicated by: Mirna Džamonja
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society