Open problems

Some places to find interesting graph theory conjectures:

The particular problems below are ones that I either have worked on in the past or would like to work on in the future.

Cops and robbers

If G is an n-vertex graph, then the cop number of G is in O(√n). [Meyniel, 1985]
The cop number of any graph embeddable on the torus is at most 3. [Andreae, 1986]

Induced subgraphs

Every graph G contains an induced subgraph H such that (a) |V(H)| ≤ ⌈|V(G)|/2⌉, and (b) for every v ∈ V(H), d_H(v) ≥ ⌊d_G(v)/2⌋. [Verstraëte]

Hamiltonian cycles

There is no 4-regular graph containing precisely one Hamiltonian cycle. [Sheehan, 1975]
There exists some constant t such that every t-tough graph is Hamiltonian. [Chvátal, 1973]

Colouring & related concepts

If every path in a graph G induces a 3-colourable subgraph, then G is c-colourable for some constant c. [Gyárfás, 1997]
(1-2-3 Conjecture) For any connected graph G on at least 3 vertices, the edges of G can be weighted from {1,2,3} such that adjacent vertices receive distinct sums of incident edge weights. [Karoński, Łuczak, Thomason, 2004]