pith. sign in

arxiv: 1812.02904 · v1 · pith:R6WOK2HEnew · submitted 2018-12-07 · 🧮 math.CO

Sequentially embeddable graphs

classification 🧮 math.CO
keywords embeddingplanarsequentialgraphverticesadjacentcallcolorable
0
0 comments X
read the original abstract

We call a (not necessarily planar) embedding of a graph $G$ in the plane \emph{sequential} if its vertices lie in $\mathbb Z^2$ and the line segments between adjacent vertices contain no interior integer points. In this note, we prove (i) a graph $G$ has a sequential embedding if and only if $G$ is 4-colorable, and (ii) if $G$ is planar, then $G$ has a sequential planar embedding.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.