Graph-Coloring and Choice a Note on a Note by Shelah and Soifer

If AC(2), the axiom of choice for families of 2-element sets, or AC(R), the axiom of choice for families of non-empty subsets of R, hold, then G is 2-colorable.

For every cardinal c and for every c-coloring f : G → c each of the coloring sets f ⁻¹(i) is either non-measurable or of measure zero.

For every 2-coloring f : G → 2 both coloring sets f ⁻¹(0) and f ⁻¹(1) are non-measurable.

For every n-coloring f : G → n where n < ℵ₀, there exists a non-measurable coloring set f ⁻¹(i).

If CC(R), the axiom of choice for countable families of non-empty subsets of R, holds, then for every ℵ₀-coloring f : G → ℵ₀ there exists a non-measurable coloring set f ⁻¹(i).

If AD, the axiom of determinateness, holds then, for any cardinal c ≤ ℵ₀, the graph G has no c-coloring.