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
Graph Theory » Graph Algorithms

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

Problem   Does there exist a polynomial time algorithm which takes as input a graph $ G $ and for every vertex $ v \in V(G) $ a subset $ \ell(v) $ of $ \{1,2,3,4\} $, and decides if there exists a partition of $ V(G) $ into $ \{A_1,A_2,A_3,A_4\} $ so that $ v \in A_i $ only if $ i \in \ell(v) $ and so that $ A_1,A_2 $ are independent, $ A_4 $ is a clique, and there are no edges between $ A_1 $ and $ A_3 $?

Keywords: list partition; polynomial algorithm

Posted by mdevos
updated May 18th, 2010
1 comment
Graph Theory » Topological G.T. » Planar graphs

What is the largest graph of positive curvature? ★

Author(s): DeVos; Mohar

Problem   What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?

Keywords: curvature; planar graph

Posted by mdevos
updated August 30th, 2011
2 comments
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