Open Problem Garden

Graph Theory » Coloring » Vertex coloring

Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

Conjecture If $G,H$ are simple finite graphs, then $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$ .

Here $G \times H$ is the tensor product (also called the direct or categorical product) of $G$ and $H$ .

Keywords: categorical product; coloring; homomorphism; tensor product

Posted by mdevos
updated March 1st, 2020

5 comments

Edge Reconstruction Conjecture ★★★

Author(s): Harary

Conjecture

Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs

Keywords: reconstruction

Posted by melch
updated May 23rd, 2008

add new comment

Nearly spanning regular subgraphs ★★★

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.