Open Problem Garden

Characterizing (aleph_0,aleph_1)-graphs ★★★

Call a graph an $(\aleph_0,\aleph_1)$ -graph if it has a bipartition $(A,B)$ so that every vertex in $A$ has degree $\aleph_0$ and every vertex in $B$ has degree $\aleph_1$ .

Problem Characterize the $(\aleph_0,\aleph_1)$ -graphs.

Keywords: binary tree; infinite graph; normal spanning tree; set theory

Posted by mdevos
updated November 24th, 2011

2 comments

Diestel, Reinhard

Graph Theory » Coloring

4-regular 4-chromatic graphs of high girth ★★

Author(s): Grunbaum

Problem Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?

Keywords: coloring; girth

Posted by mdevos
updated January 29th, 2012

2 comments

Graph Theory » Probabilistic G.T.

Coloring random subgraphs ★★

Author(s): Bukh

If $G$ is a graph and $p \in [0,1]$ , we let $G_p$ denote a subgraph of $G$ where each edge of $G$ appears in $G_p$ with independently with probability $p$ .

Problem Does there exist a constant $c$ so that ${\mathbb E}(\chi(G_{1/2})) > c \frac{\chi(G)}{\log \chi(G)}$ ?

Keywords: coloring; random graph

Posted by mdevos
updated June 4th, 2009

1 comment

Bukh, Boris

random graph

Graph Theory » Basic G.T.

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem Let $G$ be a perfect graph on $n$ vertices. Is it true that either $G$ or $\bar{G}$ contains a complete bipartite subgraph with bipartition $(A,B)$ so that $|A|, |B| \ge n^{1 - o(1)}$ ?