Vertigan, Dirk

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

Syndicate content