Problems

Problem of the month

Starting with May 2007, I will be posting new problems into the Open Problem Garden which was designed in SFU in 2006/07 by Matt DeVos and Robert Samal and included discussions of our research graph theory group at SFU. The Open Problem Garden is a Wikipedia-type forum devoted to open problems in Mathematics and with its current orientation to cover at least the area of graph theory. Most of my older problems will be added over time to this site.

• Flow polynomial at 5.5 (Late Spring 2007)
• Hamiltonicity of infinite graphs (Early Spring 2007)
• Laplacian degrees of a graph (December 2006)
• Laplacian coefficients and trees (September 2006)
• Hirsch Conjecture (Summer 2006)
• Bollobas-Leader Conjecture (Late Spring 2006)
• Olson's Conjecture (Spring 2006)
• Seymour's Second Neighborhood Conjecture (Winter 2006)

Go to the Problem of the month archives.

Problems from the book Graphs on Surfaces

Some Web pages with mathematical problems

• Open Problem Garden
• Problems I like - by Matt DeVos [temporarily unavailable]
• Problems in Topological Graph Theory maintained by Dan Archdeacon
• Open problems in Graph Theory by Stephen C. Locke
• Open problems (SIAM) by Doug West
• Open problems - Graph theory and combinatorics (collected by Doug West)
• Open problems in Graph Theory - DIMACS
• MathSoft unsolved problems

Problem of the month (archives)

• Crossing number of the complete graph (April 2001)
• Crossing number of the complete bipartite graph (April 2001)
• Crossing number of the hypercube (April 2001)
• Barnette's Conjecture (May 2001)
• Grunbaum's Edge-Coloring Conjecture (June 2001)
• Matchings in vertex transitive graphs (July 2001)
• Δ-edge-critical graphs and list colorings (August 2001)
• The chromatic number of the Unit Distance Graph (September 2001)
• Berge-Fulkerson Conjecture (October 2001)
• Hamiltonicity of graphs of convex polytopes (November 2001)
• Contractible edges in 5-connected graphs (December 2001)
• Choosability for the circular chromatic number (January 2002) [partially solved by X. Zhu]
• Are 3-connected planar graphs determined by their spectral properties? (February 2002)
• One Factorization and Hamiltonian Factorization Conjecture (March 2002)
• Fowler's Conjecture on eigenvalues of (3,6)-polyhedra (April 2002)
• Local colorings of triangulations (May 2002)
• Light infinite paths in infinite planar graphs (June 2002)
• Acyclic partitions of planar digraphs (July 2002)
• Induced forests in planar graphs (August 2002)
• Steiner triple systems and flexibility of embeddings of K_n (September - December 2002) [Comments by Mark Ellingham added in Dec.04]
• Can flow polynomials have large (real) roots? (January 2003)
• 5-Choosability of graphs on a fixed surface (February 2003) [Conjecture 2 solved by M. DeVos, K.-I. Kawarabayashi and B. Mohar in June 2005]
• The Strong Circular 5-Flow Conjecture (March and April 2003) [solved by E. Mačajova and A. Raspaud]
• Eigenvalue-nonhamiltonian graphs (May 2003) [solved by Chris Godsil and Gordon Royle]
• (r,s)-edge-choosability of cubic graphs (June 2003) [partial answer provided by Jessica McDonald and Reza Naserasr]
• Edge-coloring dual complete maps (Summer 2003)
• A relaxation of the Hadwiger Conjecture (Fall 2003)
• Long paths in vertex-transitive graphs (Winter 2003/04)
• Graphs of 4-polytopes (Early Spring 2004)
• Snarks on the projective plane (Late Spring 2004)
• Largest planar graph with positive combinatorial curvature (Summer 2004) [Added in January 2005: a solution found by Tamas Reti, a relaxed problem has been proposed.]
• (3l + 1)-Conjecture (Fall 2004) - submitted by D. Kral, T. Madaras and R. Škrekovski
• Graph Theory @ Oberwolfach 2005, Part 1 (Early Winter 2005)
• Graph Theory @ Oberwolfach 2005, Part 2 (Late Winter 2005)
• Removable paths conjectures (Spring 2005) - communicated by Matthias Kriesell
• Genus of Paley graphs (Early Summer 2005)
• Genus spectrum of regular maps (Late Summer 2005)
• Testing how nonplanar is a graph (Fall 2005) - proposed jointly with Sergio Cabello

Revised: June 08, 2007.