Open Problem Garden

Author(s): Alon; Mubayi

Conjecture For every $\epsilon > 0$ and every positive integer $k$ , there exists $r_0 = r_0(\epsilon,k)$ so that every simple $r$ -regular graph $G$ with $r \ge r_0$ has a $k$ -regular subgraph $H$ with $|V(H)| \ge (1- \epsilon) |V(G)|$ .

Keywords: regular; subgraph

Posted by mdevos
updated May 22nd, 2008

add new comment

Graph Theory » Topological G.T. » Coloring

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $G$ is $k$ -degenerate if every subgraph of $G$ has a vertex of degree $\le k$ .

Conjecture Every simple planar graph has a 5-coloring so that for $1 \le k \le 4$ , the union of any $k$ color classes induces a $(k-1)$ -degenerate graph.