Open Problem Garden

Graph Theory » Coloring

List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

Conjecture If $G$ is the total graph of a multigraph, then $\chi_\ell(G)=\chi(G)$ .

Keywords: list coloring; Total coloring; total graphs

Posted by Jon Noel
updated August 29th, 2013

add new comment

Geometry

Partitioning the Projective Plane ★★

Author(s): Noel

Throughout this post, by projective plane we mean the set of all lines through the origin in $\mathbb{R}^3$ .

Definition Say that a subset $S$ of the projective plane is octahedral if all lines in $S$ pass through the closure of two opposite faces of a regular octahedron centered at the origin.

Definition Say that a subset $S$ of the projective plane is weakly octahedral if every set $S'\subseteq S$ such that $|S'|=3$ is octahedral.

Conjecture Suppose that the projective plane can be partitioned into four sets, say $S_1,S_2,S_3$ and $S_4$ such that each set $S_i$ is weakly octahedral. Then each $S_i$ is octahedral.

Keywords: Partitioning; projective plane

Posted by Jon Noel
updated August 27th, 2013

add new comment

projective plane

Graph Theory » Basic G.T. » Connectivity

Conjecture Let $G$ be a graph and let $T\subseteq V(G)$ such that for any pair $u,v\in T$ there are $2k$ edge-disjoint paths from $u$ to $v$ in $G$ . Then $G$ contains $k$ edge-disjoint trees, each of which contains $T$ .