Semialgebraic graphs having countable list-chromatic numbers

Schmerl, James

doi:10.1090/proc/12832

Semialgebraic graphs having countable list-chromatic numbers
HTML articles powered by AMS MathViewer

by James H. Schmerl

Proc. Amer. Math. Soc. 144 (2016), 1429-1438

DOI: https://doi.org/10.1090/proc/12832

Published electronically: July 30, 2015

PDF | Request permission

Abstract:

For $n \geq 1$ and a countable, nonempty set $D$ of positive reals, the $D$-distance graph $\textbf {X}_n(D)$ is the graph on Euclidean 𝑛-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 $\textbf {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

N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), no. 2, 125–134. MR 1179249, DOI 10.1007/BF01204715
P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99. MR 193025, DOI 10.1007/BF02020444
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, DOI 10.1007/BF02579156
Tommy R. Jensen and Bjarne Toft, Choosability versus chromaticity—the plane unit distance graph has a $2$-chromatic subgraph of infinite list-chromatic number, Geombinatorics 5 (1995), no. 2, 45–64. Appendix 1 by Leonid S. Mel′nikov and Vadim G. Vizing and Appendix 2 by Noga Alon. MR 1352332
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
Peter D. Johnson Jr., The choice number of the plane, Geombinatorics 3 (1994), no. 4, 122–128. MR 1268721
Péter Komjáth, A decomposition theorem for $\textbf {R}^n$, Proc. Amer. Math. Soc. 120 (1994), no. 3, 921–927. MR 1169038, DOI 10.1090/S0002-9939-1994-1169038-0
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, DOI 10.1007/s00454-009-9228-5
Péter Komjáth, The list-chromatic number of infinite graphs, Israel J. Math. 196 (2013), no. 1, 67–94. MR 3096584, DOI 10.1007/s11856-012-0145-6
James H. Schmerl, The list-chromatic number of Euclidean space, Geombinatorics 5 (1995), no. 2, 65–68. MR 1352333
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, DOI 10.2178/jsl.7704060
Alexander Soifer, The mathematical coloring book, Springer, New York, 2009. Mathematics of coloring and the colorful life of its creators; With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau. MR 2458293