6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What's your definition of 'planarity'? I would expect that any reasonable definition here would lead to a well-ordering on the graph nodes... $\endgroup$ – Steven Stadnicki Mar 4 at 19:12
  • $\begingroup$ 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? $\endgroup$ – fkenter2 Mar 4 at 19:35
  • 2
    $\begingroup$ 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? $\endgroup$ – user6976 Mar 4 at 19:53
  • $\begingroup$ @Mark One might want to consider rather than a global embedding only local ones. $\endgroup$ – Andrés E. Caicedo Mar 4 at 19:56
  • 1
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Mar 4 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.