Open Problem Garden

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

Kriesell, Matthias

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$ .

Keywords: Disjoint paths; edge-connectivity; spanning trees

Posted by Jon Noel
updated August 25th, 2013

add new comment

maximum clique

Graph Theory » Coloring » Vertex coloring

2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

Conjecture If $G$ is a non-empty graph containing no induced odd cycle of length at least $5$ , then there is a $2$ -vertex colouring of $G$ in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning

Posted by Jon Noel
updated August 25th, 2013

add new comment