Axiom of choice and chromatic number: Examples on the plane

DOI10.1016/J.JCTA.2004.01.001MaRDI QIDQ598462zbMATH OpenOpenAlexWikidataFDO

Authors Alexander Soifer, S. Shelah

Publication date 6 August 2004

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcta.2004.01.001

zbMATH Keywords

axiom of choicechromatic numberinfinite graphs

Mathematics Subject Classification ID

Axiom of choice and related propositions (03E25) Coloring of graphs and hypergraphs (05C15)

Review text

Let the vertices of the graph \(G_2\) be \({\mathbb R}^2\) with \(x\) and \(y\) joined iff \(x-y\in {\mathbb Q}^2+a\) where \(a\) is either \((\sqrt{2},0)\), \((0,\sqrt{2})\), \((\sqrt{2},\sqrt{2})\), or \((-\sqrt{2},\sqrt{2})\). It is shown that if the axiom of choice holds then the chromatic number of \(G_2\) is 4. If, however, the countable axiom of choice holds and every set of reals is Lebesgue measurable then, by Steinhaus's theorem, \(G_2\) is not even countably chromatic. A similar argument works if \(x\) and \(y\) are joined iff \(x-y\in {\mathbb Q}^2+\bigl\{(\sqrt{2},0),(0,\sqrt{2})\bigr\}\)

Recommendations

• Axiom of choice and chromatic number of the plane
• Graph-Coloring and Choice a Note on a Note by Shelah and Soifer
• Axiom of choice and chromatic number of \(R^n\)
• scientific article; zbMATH DE number 2112063
• scientific article; zbMATH DE number 2170328

Cites work

• A model of set-theory in which every set of reals is Lebesgue measurable
• A system of axiomatic set theory. Part III. Infinity and enumerability. Analysis
• Axiom of choice and chromatic number of the plane
• scientific article; zbMATH DE number 51916 (Why is no real title available?)
• scientific article; zbMATH DE number 2042230 (Why is no real title available?)
• scientific article; zbMATH DE number 2140325 (Why is no real title available?)
• scientific article; zbMATH DE number 3068973 (Why is no real title available?)
• The axiom of choice
• Unsolved problems in geometry

Cited in

(14)

• Axiom of choice and chromatic number of \(R^n\)
• On configurations of solid balls in 3-space: chromatic numbers and knotted cycles
• Unit distance graphs with ambiguous chromatic number
• Orthogonal colorings of the sphere
• scientific article; zbMATH DE number 2170328 (Why is no real title available?)
• scientific article; zbMATH DE number 2094516 (Why is no real title available?)
• scientific article; zbMATH DE number 2112063 (Why is no real title available?)
• Applications of the axiom of choice to constructions in Euclidean spaces
• On a generalization of the Hadwiger-Nelson problem
• Distance graphs whose chromatic number is affected by the underlying set theory
• Graph-Coloring and Choice a Note on a Note by Shelah and Soifer
• Coloring distance graphs on the plane
• Brooks' type theorems for coloring parameters of locally finite graphs and Kőnig's Lemma
• On Rado's boundedness conjecture

This page was built for publication: Axiom of choice and chromatic number: Examples on the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598462)