Ding, Guoli

Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

\begin{conjecture} Let $r \ge 2$ be an integer and let $H$ be a minor minimal \Def{clutter} with $\frac{1}{r}\tau_r(H) < \tau(H)$. Then either $H$ has a $J_k$ minor for some $k \ge 2$ or $H$ has Lehman's property. \end{conjecture}

Keywords: clutter; covering; MFMC property; packing

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