The Friday afternoon Algorithms Seminar at Clemson has been a rich source of interesting problems over the past twelve years, as have many discrete math conferences, including our twelve Clemson mini-Conferences on Discrete Mathematics. During this time I have compiled an on-going list of open problems, which fascinate me for their apparent difficulty, their simplicity of statement and their inherent interest. Motivated by numerous requests for an updated version of this list, I am finally taking the time to update it and make it available to anyone who would like to read or copy it.
For each of the following problems I will attempt to identify the originators and the approximate time of origin. If you can provide me with any historical corrections or additions to any of the problems in this list, please let me know.
You will note that I have not yet provided many literature citations; it will take a LONG time to provide all of the relevant references. I hope to be able to include more and more of this information in the future. So please consider this to be a 'working' document, which will repeatedly be updated.
Most of these problems are stated in the Garey and Johnson format for NP-complete problems. Unless stated otherwise, by 'Open' I mean that the complexity of the problem is not known to me (no NP-completeness proof exists), neither does any algorithm exist for solving the problem, or no solution is known to exist.
Finally, let me add that these are simply problems that fascinate and interest me; obviously I have my own biases. Certainly everyone has their own favorite problems. The problems in this list are broken down into several types:
algorithms and complexity problems
broadcasting and gossiping problems
problems on chessboards
coloring and partition problems
problems on cycles and Hamiltonian cycles
domination, irredundance and independence
problems
graph theory problems
miscellaneous problems