Some places to find interesting graph theory conjectures:

- Open Problem Garden
- Doug West’s open problem page and archives

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]