Open Problem Garden

A nowhere-zero point in a linear mapping ★★★

Author(s): Jaeger

Conjecture If ${\mathbb F}$ is a finite field with at least 4 elements and $A$ is an invertible $n \times n$ matrix with entries in ${\mathbb F}$ , then there are column vectors $x,y \in {\mathbb F}^n$ which have no coordinates equal to zero such that $Ax=y$ .

Keywords: invertible; nowhere-zero flow

Posted by mdevos
updated March 8th, 2007

add new comment

Graph Theory » Basic G.T. » Connectivity

Partitioning edge-connectivity ★★

Author(s): DeVos

Question Let $G$ be an $(a+b+2)$ -edge-connected graph. Does there exist a partition $\{A,B\}$ of $E(G)$ so that $(V,A)$ is $a$ -edge-connected and $(V,B)$ is $b$ -edge-connected?

Keywords: edge-coloring; edge-connectivity

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Coloring » Edge coloring

Acyclic edge-colouring ★★

Author(s): Fiamcik

Conjecture Every simple graph with maximum degree $\Delta$ has a proper $(\Delta+2)$ -edge-colouring so that every cycle contains edges of at least three distinct colours.

Keywords: edge-coloring

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Coloring » Edge coloring

Packing T-joins ★★

Author(s): DeVos

Conjecture There exists a fixed constant $c$ (probably $c=1$ suffices) so that every graft with minimum $T$ -cut size at least $k$ contains a $T$ -join packing of size at least $(2/3)k-c$ .

Keywords: packing; T-join

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Coloring » Edge coloring

Petersen coloring conjecture ★★★

Author(s): Jaeger

Conjecture Let $G$ be a cubic graph with no bridge. Then there is a coloring of the edges of $G$ using the edges of the Petersen graph so that any three mutually adjacent edges of $G$ map to three mutually adjancent edges in the Petersen graph.

Keywords: cubic; edge-coloring; Petersen graph

Posted by mdevos
updated November 24th, 2011

2 comments

Graph Theory » Basic G.T. » Matchings

The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

Conjecture If $G$ is a bridgeless cubic graph, then there exist 6 perfect matchings $M_1,\ldots,M_6$ of $G$ with the property that every edge of $G$ is contained in exactly two of $M_1,\ldots,M_6$ .

Keywords: cubic; perfect matching

Posted by mdevos
updated November 23rd, 2011

9 comments

Graph Theory » Basic G.T. » Cycles

Decomposing eulerian graphs ★★★

Author(s):

Conjecture If $G$ is a 6-edge-connected Eulerian graph and $P$ is a 2-transition system for $G$ , then $(G,P)$ has a compaible decomposition.

Keywords: cover; cycle; Eulerian

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

Faithful cycle covers ★★★

Author(s): Seymour

Conjecture If $G = (V,E)$ is a graph, $p : E \rightarrow {\mathbb Z}$ is admissable, and $p(e)$ is even for every $e \in E(G)$ , then $(G,p)$ has a faithful cover.