planar graph

Bounded colorings for planar graphs ★★

Author(s): Alon; Ding; Oporowski; Vertigan

\begin{question} Does there exists a fixed function $f : {\mathbb N} \rightarrow {\mathbb N}$ so that every \Def[planar]{planar graph} graph of maximum degree $d$ has a partition of its vertex set into at most three sets $\{V_1,V_2,V_3\}$ so that for $i=1,2,3$, every component of the graph induced by $V_i$ has size at most $f(d)$? \end{question}

Keywords: coloring; partition; planar graph

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $P \subseteq {\mathbb R}^2$ is $n$-\emph{universal} if every $n$ vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in $P$, and all edges are (non-intersecting) straight line segments.

\begin{question} Does there exist an $n$-universal set of size $O(n)$? \end{question}

Keywords: geometric graph; planar graph; universal set

What is the largest graph of positive curvature?

Author(s): DeVos; Mohar

\begin{problem} What is the largest connected \Def{planar graph} of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a \Def[prism]{prism (geometry)} or \Def{antiprism}? \end{problem}

Keywords: curvature; planar graph

Syndicate content