22
$\begingroup$

Is there something similar to the Kourovka Notebook for graph theory (or anyway an organized, possibly commented, collection of conjectures and open problems)?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
19
$\begingroup$

The largest section in the open problem garden is about graph theory. The book Erdös on Graphs with its living version might be interesting as well.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Very interesting website. Thank you. $\endgroup$
    – user60665
    Commented Dec 26, 2014 at 0:05
9
$\begingroup$

I think the answers already given by Thomas Kalinowski are more comprehensive, but Douglas B. West maintains another collection of open problems in graph theory at http://www.math.illinois.edu/~dwest/openp/ (Wayback Machine) and there are also several graph theory problems listed at List of unsolved problems in mathematics § Graph theory on Wikipedia.

Improve this answer
$\endgroup$
0
7
$\begingroup$

See Graffiti by Siemion Fajtlowicz. But the great majority of these problems (mainly on graph theory) were not by Fajtlowicz directly but by Graffiti itself (only some were jointly obtained by Graffiti and Fajtlowicz), while Graffiti is a computer program created by Siemion. (Paul Erdos liked the Graffiti conjectures, so you may too). :-)

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Dal -- you're welcome. There is quite a bit about Graffiti on Internet, and you may also contact S.F. himself. If somehow I can help I'd try. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Dec 26, 2014 at 11:13
4
$\begingroup$

A list of about 60 algorithmic problems pertaining to trees are given in the paper by Stephen T. Hedetniemi (Wayback Machine, journal website). Some of the discussion in the paper can be extended to questions on graphs of bounded treewidth.

Improve this answer
$\endgroup$
1
$\begingroup$

Here is a nice problem about graphs: it is true that every Cayley graph of every finitely generated cancellative semigroup must have either $1$, or $2$, or $\infty$-many ends (number of connected components looked from the infinity perspective, roughly speaking). But yet, no analog of Stallings Theorem for finitely generated cancellative semigroups is known. It would be fun to know.

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ This does not address the question that was asked $\endgroup$
    – Yemon Choi
    Commented Jan 1, 2015 at 15:31

You must log in to answer this question.