domination

Domination in cubic graphs ★★

Author(s): Reed

\begin{problem} Does every 3-connected cubic graph $G$ satisfy $\gamma(G) \le \lceil |G|/3 \rceil$ ? \end{problem}

Keywords: cubic graph; domination

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

\begin{conjecture} Every sufficiently large plane triangulation $G$ has a dominating set of size $\le \frac{1}{4} |V(G)|$. \end{conjecture}

Keywords: coloring; domination; multigrid; planar graph; triangulation