Home

Recent Activity

Graph Theory » Algebraic G.T.

Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Problem   Does every connected vertex-transitive graph have a Hamiltonian path?

Keywords: cycle; hamiltonian; path; vertex-transitive

Posted by mdevos
updated March 18th, 2007
add new comment
Graph Theory » Algebraic G.T.

57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

Question   Does there exist a 57-regular graph with diameter 2 and girth 5?

Keywords: cage; Moore graph

Posted by mdevos
updated March 18th, 2007
add new comment
Number Theory » Combinatorial N.T.

Few subsequence sums in Z_n x Z_n ★★

Author(s): Bollobas; Leader

Conjecture   For every $ 0 \le t \le n-1 $, the sequence in $ {\mathbb Z}_n^2 $ consisting of $ n-1 $ copes of $ (1,0) $ and $ t $ copies of $ (0,1) $ has the fewest number of distinct subsequence sums over all zero-free sequences from $ {\mathbb Z}_n^2 $ of length $ n-1+t $.

Keywords: subsequence sum; zero sum

Posted by mdevos
updated March 10th, 2007
add new comment
Number Theory » Combinatorial N.T.

Olson's Conjecture ★★

Author(s): Olson

Conjecture   If $ a_1,a_2,\ldots,a_{2n-1} $ is a sequence of elements from a multiplicative group of order $ n $, then there exist $ 1 \le j_1 < j_2 \ldots < j_n \le 2n-1 $ so that $ \prod_{i=1}^n a_{j_i} = 1 $.

Keywords: zero sum

Posted by mdevos
updated March 10th, 2007
add new comment
Graph Theory » Basic G.T. » Minors

Jorgensen's Conjecture ★★★

Author(s): Jorgensen

Conjecture   Every 6-connected graph without a $ K_6 $ minor is apex (planar plus one vertex).

Keywords: connectivity; minor

Posted by mdevos
updated March 10th, 2007
add new comment
Graph Theory » Basic G.T. » Minors

Highly connected graphs with no K_n minor ★★★

Author(s): Thomas

Problem   Is it true for all $ n \ge 0 $, that every sufficiently large $ n $-connected graph without a $ K_n $ minor has a set of $ n-5 $ vertices whose deletion results in a planar graph?

Keywords: connectivity; minor

Posted by mdevos
updated March 10th, 2007
add new comment
Combinatorics » Matrices

The Alon-Tarsi basis conjecture ★★

Author(s): Alon; Linial; Meshulam

Conjecture   If $ B_1,B_2,\ldots B_p $ are invertible $ n \times n $ matrices with entries in $ {\mathbb Z}_p $ for a prime $ p $, then there is a $ n \times (p-1)n $ submatrix $ A $ of $ [B_1 B_2 \ldots B_p] $ so that $ A $ is an AT-base.

Keywords: additive basis; matrix

Posted by mdevos
updated March 8th, 2007
add new comment
Combinatorics » Matrices

The permanent conjecture ★★

Author(s): Kahn

Conjecture   If $ A $ is an invertible $ n \times n $ matrix, then there is an $ n \times n $ submatrix $ B $ of $ [A A] $ so that $ perm(B) $ is nonzero.

Keywords: invertible; matrix; permanent

Posted by mdevos
updated March 8th, 2007
add new comment
Combinatorics » Matrices

The additive basis conjecture ★★★

Author(s): Jaeger; Linial; Payan; Tarsi

Conjecture   For every prime $ p $, there is a constant $ c(p) $ (possibly $ c(p)=p $) so that the union (as multisets) of any $ c(p) $ bases of the vector space $ ({\mathbb Z}_p)^n $ contains an additive basis.

Keywords: additive basis; matrix

Posted by mdevos
updated March 8th, 2007
add new comment
Combinatorics » Matrices

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

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

Conjecture   Every bridgeless graph has a (5,2)-cycle-cover.

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

The circular embedding conjecture ★★★

Author(s): Haggard

Conjecture   Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle.

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Coloring » Nowhere-zero flows

Unit vector flows ★★

Author(s): Jain

Conjecture   For every graph $ G $ without a bridge, there is a flow $ \phi : E(G) \rightarrow S^2 = \{ x \in {\mathbb R}^3 : |x| = 1 \} $.

Conjecture   There exists a map $ q:S^2 \rightarrow \{-4,-3,-2,-1,1,2,3,4\} $ so that antipodal points of $ S^2 $ receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.

Keywords: nowhere-zero flow

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Coloring » Nowhere-zero flows

A homomorphism problem for flows ★★

Author(s): DeVos

Conjecture   Let $ M,M' $ be abelian groups and let $ B \subseteq M $ and $ B' \subseteq M' $ satisfy $ B=-B $ and $ B' = -B' $. If there is a homomorphism from $ Cayley(M,B) $ to $ Cayley(M',B') $, then every graph with a B-flow has a B'-flow.

Keywords: homomorphism; nowhere-zero flow; tension

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Coloring » Nowhere-zero flows

The three 4-flows conjecture ★★

Author(s): DeVos

Conjecture   For every graph $ G $ with no bridge, there exist three disjoint sets $ A_1,A_2,A_3 \subseteq E(G) $ with $ A_1 \cup A_2 \cup A_3 = E(G) $ so that $ G \setminus A_i $ has a nowhere-zero 4-flow for $ 1 \le i \le 3 $.

Keywords: nowhere-zero flow

Posted by mdevos
updated March 7th, 2007
add new comment