Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

\begin{question} Is there a constant $c$ such that every $n$-vertex $K_t$-minor-free graph has at most $c^tn$ cliques? \end{question}

Keywords: clique; graph; minor

Seagull problem ★★★

Author(s): Seymour

\begin{conjecture} Every $n$ vertex graph with no independent set of size $3$ has a complete graph on $\ge \frac{n}{2}$ vertices as a minor. \end{conjecture}

Keywords: coloring; complete graph; minor

Seymour's self-minor conjecture ★★★

Author(s): Seymour

\begin{conjecture} Every infinite graph is a proper \Def[minor]{minor (graph theory)} of itself. \end{conjecture}

Keywords: infinite graph; minor

Consecutive non-orientable embedding obstructions ★★★


\begin{conjecture} Is there a graph $G$ that is a minor-minimal obstruction for two non-orientable surfaces? \end{conjecture}

Keywords: minor; surface

Jorgensen's Conjecture ★★★

Author(s): Jorgensen

\begin{conjecture} Every 6-\Def[connected]{connectivity (graph theory)} graph without a \Def[$K_6$]{complete graph} \Def[minor]{minor (graph theory)} is apex (planar plus one vertex). \end{conjecture}

Keywords: connectivity; minor

Highly connected graphs with no K_n minor ★★★

Author(s): Thomas

\begin{problem} Is it true for all $n \ge 0$, that every sufficiently large $n$-\Def[connected]{connectivity (graph theory)} graph without a \Def[$K_n$]{complete graph} \Def[minor]{minor (graph theory)} has a set of $n-5$ vertices whose deletion results in a \Def{planar graph}? \end{problem}

Keywords: connectivity; minor

4-flow conjecture ★★★

Author(s): Tutte

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph with no \Def[Petersen]{petersen graph} \Def[minor]{minor (graph theory)} has a \Def[nowhere-zero]{nowhere-zero flows} 4-flow. \end{conjecture}

Keywords: minor; nowhere-zero flow; Petersen graph

Syndicate content