Open Problems in Complexity and Graph Theory

Links

Warning, several of the following sites aren't regularly updated and some of the problems may no longer be open. As you should be doing anyhow, always, at least, skim the papers on the topic before trying to solve it on your own, save for a few minutes to hours of initial pondering.
http://en.wikipedia.org/wiki/List_of_open_problems_in_computer_science
http://maven.smith.edu/~orourke/TOPP/Welcome.html
http://compgeom.cs.uiuc.edu/~jeffe/open/
http://www.math.fau.edu/locke/Unsolved.htm
Algorithmic Theory of Random graphs - Frieze and McDiarmid
http://garden.irmacs.sfu.ca/
The Homepage of Nearest Neighbors and Similarity Search, Open Problems
http://www.geocities.com/ednitou/
http://www.ics.uci.edu/~eppstein/junkyard/open.html
Some Open Problems [in graph algorithms]
http://users.encs.concordia.ca/~chvatal/perfect/problems.html
A summary of The diameter of random sparse graphs by W. Aiello, Fan Chung and Lincoln Lu
http://www.cs.clemson.edu/~hedet/preface.html
http://www.brics.dk/LS/01/1/
http://algo.inria.fr/AofA/Problems/index.html
http://tlca.di.unito.it/opltlca/
http://weblog.fortnow.com/2003/03/berman-hartmanis-isomorphism.html
http://in-theory.blogspot.com/2006/10/limitations-of-linear-and-semidefinite.html
Open Problems for Undergraduates
Open Problems - Graph Theory and Combinatorics collected and maintained by Douglas B. West

Some of the most noteworthy problems in my opinion

• Try to separate P from PSPACE. It is believed that P != NP. If this is true, then we also have that P != NP^NP, P != NP^NP^NP, ..., P != PH, P != P^#P, and P != PSPACE = NPSPACE. In the light of this collapse, it is naive to try to directly show that P != NP. In fact, it goes against a basic problem solving technique: find easier subproblems and solve those first; use the ideas from those solutions to attack the main problem. For this question, we have the added bonus that settling P != PSPACE is a life-time achievement in its own right. Of course, any other consequence of P != NP (or P=NP if preferred) would also do.
• The Unique Games Conjecture.
• What is the MAX-SNP(closure)-equivalence for PSPACE (or other classes) with respect to approximability?

Open problems for undergrads and advanced high schoolers

Here you may find some problems that are understandable by undergrads and advanced high schoolers, and for which the chance for these of solving is comparable to that of a more experienced researcher (without implying that the chance is substantial). Note that these problem are not necessarily the complete mathematical problems but rather particularly simple and important subproblems that researchers are still struggling with.

• Open Problem Garden, sorted for undergrads
• Let a₁, a₂, a₃, a₄, a₅ be positive integers. Can 3125 five-dimensional boxes of sides a₁ x a₂ x a₃ x a₄ x a₅ be fit into a five-dimensional hypercube with sides of length a₁ + a₂ + a₃ + a₄ + a₅? To start this task, you may want to show that 3³=27 three-dimensional boxes of sides a₁ x a₂ x a₃ can be fit into a three-dimensional cube with sides of length a₁ + a₂ + a₃. (might be possible to solve by programming) More info: Open Problem Garden.
• Let the degree of a vertex in a graph be its number of incident vertices ("neighbors"). A triangle is the graph on three vertices that has three edges. We say that a graph is k-colorable iff each vertex in the graph can be assigned a number ("color") in {1, 2, ..., k} and no two adjacent vertices have the same color. Construct a k-colorable graph with maximum degree six containing no triangles, or show that no such graph exists. Open Problem Garden
• Let t₁, t₂, ..., t_n be real values between 1 and n+1. Define for 1 ≤ i ≤ n the independent random variable X_i that attains 0 with probability 1 - 1/t_i and t_i with probability 1/t_i. Show that P(X₁ + X₂ + ... + X_n < n+1) > 1/8. It has been conjectured that this holds even for ≥ 1/e where e is the natural number 2.718... More info: Open Problem Garden.
• Find an incomplete sequence on The On-Line Encyclopedia of Integer Sequences and compute the next number (programming).