How do we describe a construction of a 2-colorable graph where the degree of every vertex is greater than or equal to (|V|-1)/2? Based on that, what can be said about the dependence of maximum vertex-degree on k-colorability of a graph?
My first thought is that in order for a vertex to connect to every single other vertex on a graph, it's degree would have to be |V|-1. But since we're looking at half of that in (|V|-1)/2, it would only be connected to half the vertices in the graph, so if this was the case for all vertices in G we'd be constructing a 2-colorable bipartite graph (is my thought).
I'm not too sure how to deal with the second part, however. I know that in a graph there can be n different colors for k given n vertices in a row and we need to add colors whenever there are adjacent vertices, but I can't figure out how the maximum vertex-degree in particular effects how many colors we can use for a graph.
A complete bipartite graph where one side has $\lceil\frac{|V|}{2}\rceil$ vertices and the other side has $\lfloor\frac{|V|}{2}\rfloor$ vertices, is 2-colorable and meets the desired lower bound on the minimum degree.
So a graph may have very large minimum degree $D$ and be $k$-colorable for some $k <<D$--as the above example illustrates. But all graphs with maximum degree $D-1$ are $D$-colorable. In fact, all graphs $G$ with no $D$-core i.e., there is no subgraph of $G$ where every vertex has degree at least $D$--are also $D$-colorable.