After some more thinking, I found a simple solution. We get it very quickly from two results which are well-known in graph theory, though for completeness I will include their proofs.
Lemma 1. A graph $G$ with minimum degree $k$ contains a cycle of length at least $k+1$.
Proof. Take the longest path $v_0, v_1, v_2, \dots, v_\ell$ in $G$. The vertex $v_0$ has at least $k$ neighbors, and all of them must be other vertices on the path, because otherwise we could extend the path and make it even longer. The last of $v_0$'s neighbors on the path must be at least as far as $v_k$ (since there's $k$ of them), so we get a cycle of length at least $k+1$ by following the path from $v_0$ to $v_0$'s last neighbor, then taking the edge back to $v_0$.
Conversely, if the longest cycle in a graph $G$ has length $k$, then it has a vertex of degree $k-1$ or less. What's more, in every subgraph $H$ of $G$, the longest cycle has length $k$ or less (if it's a cycle in $H$, it's a cycle in $G$, too). So $H$ must have a vertex of degree $k-1$ or less.
A graph with this property - every subgraph has a vertex of degree $k-1$ or less - is called $(k-1)$-degenerate.
Lemma 2. A $(k-1)$-degenerate graph $G$ has chromatic number at most $k$.
Proof. We induct on the number of vertices in $G$. When $G$ has $k$ vertices or fewer, we can $k$-color $G$ by giving all the vertices different colors.
Otherwise, let $v$ be a vertex of degree $k-1$ or less. $G-v$ is also $(k-1)$-degenerate (every subgraph of $G-v$ is a subgraph of $G$) and has one fewer vertex, so by induction $G-v$ is $k$-colorable. We can $k$-color $G$ by starting with the $k$-coloring of $G-v$, then giving $v$ a color distinct from the colors on its neighbors (which eliminates at most $k-1$ options).
Putting together the two lemmas: a graph with circumference $k$ is $(k-1)$-degenerate, so it has chromatic number at most $k$. The chromatic number is at most the circumference.
Best Answer
Let the vertices of the complete graph $K_n$ be located at the vertices of a regular $n$-gon. Then the edges of $K_n$ are all possible diagonals of $n$-gon and all its sides. Now remove all sides of the $n$-gon. We obtain our graph $G$. Let $n=2019$. Suppose the vertices of $G$ are painted in $1009$ colors. Then we find three vertices colored in the same color. But then this coloring is not proper.