6

This is a follow-up to: Are infinite planar graphs still 4-colorable?

Specifically, absent the axiom of choice, is there an explicit example of an (probably uncountably) infinite planar graph that is not 4-colorable?

fkenter2
  • 61
  • What's your definition of 'planarity'? I would expect that any reasonable definition here would lead to a well-ordering on the graph nodes... – Steven Stadnicki Mar 04 '20 at 19:12
  • I suspect that any answer may depend on the definition of planarity, and I will refrain from imposing any particular definition; I am just interested in any relevant example. Why would a well-ordering of nodes be particularly important? – fkenter2 Mar 04 '20 at 19:35
  • 2
    A graph $(V, E)$ is called planar if there are maps $f: V\to \mathbb{R}^2$ and $g$ from $E$ to the set of arcs in $\mathbb{R}^2$ such that the arc correspnding to an edge $(a,b)$ connects $f(a)$ and $f(b)$ . and no two arcs $g(e)$, $g(e')$ intersect except at end points providef $e\ne e'$. Is there a different definition? –  Mar 04 '20 at 19:53
  • @Mark One might want to consider rather than a global embedding only local ones. – Andrés E. Caicedo Mar 04 '20 at 19:56
  • To the OP, such a graph would indeed have to be uncountable: otherwise we could apply Konig's Lemma (fix an enumeration of the graph and build a tree whose nodes of height $n$ correspond to four-colorings of the first $n$ nodes of the graph, and conclude that that tree is infinite via the usual four-color theorem). Interestingly, I don't at the moment see how to rule out the possibility of an uncountable-but-well-orderable example! – Noah Schweber Mar 04 '20 at 20:04
  • 1
    @StevenStadnicki Sorry, that was a blindingly stupid moment on my part. Consider the graph with vertex set $\mathbb{R}\times{1,2}$ and edge relation given by $(a,b)E(c,d)$ iff $a=c$. I don't see how this wouldn't be considered planar, but $\mathbb{R}$ isn't well-orderable in ZF alone. – Noah Schweber Mar 04 '20 at 20:06
  • If AC is true then "locally planar" should imply "planar", But if it is not true then there should be a graph $G$ which is locally planar but not planar and then $G$ should not be 4-colorable, Right? –  Mar 04 '20 at 20:12
  • @NoahSchweber That's a very good example, although it also points to a plausible path towards resolving the question (one way or the other) : can one sensibly define connectedness on a planar graph, and can the question be reduced to the corresponding question for connected graphs? – Steven Stadnicki Mar 04 '20 at 20:14
  • Also relevant: https://math.stackexchange.com/questions/712013/can-there-exist-an-uncountable-planar-graph – Steven Stadnicki Mar 04 '20 at 20:20
  • @StevenStadnicki Connectedness for large graphs can be defined as usual (existence of finite paths between any two points), and we can still get large planar connected graphs: consider the graph with vertex set the unit circle + the origin, and an edge between the origin and each point on the circle but no other edges. – Noah Schweber Mar 04 '20 at 20:25

0 Answers0