Ding, Guoli


Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let $ r \ge 2 $ be an integer and let $ H $ be a minor minimal 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.

Keywords: clutter; covering; MFMC property; packing

Bounded colorings for planar graphs ★★

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

Question   Does there exists a fixed function $ f : {\mathbb N} \rightarrow {\mathbb N} $ so that every planar 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) $?

Keywords: coloring; partition; planar graph

Syndicate content