Sparse graphs that are hard to color I am interested in knowing if there are any types of graphs that are very sparse, perhaps consisting of just connections between paths and cycles, and for which $k$-coloring is $\mathsf{NP}$-hard for some $k \in \mathbb{N}$.
I know a single cycle and path are very easy to color. Are there types of graphs that, when combined in a clever way, become hard to color? 
 A: Barbanchon proved that 3-colorability of planar graphs is NP-complete and the number of 3-colorings of a planar graph is parsimoniously #P-complete after dividing by 6.  This is a really nice hardness result that immediately implies a sparseness result, since the average valence of any planar graph is less than 6.   Although I do not really know, I suspect that his construction can yield some uniform upper bound on the valence of all vertices.
If you just want NP-hardness and bounded valence, it's easier than planarity.   The standard method to show that 3-colorability is NP-hard is to first show that 3-coloring extension is NP-hard by replacing 3-SAT clauses or even logic gates with partially colored subgraph gadgets.   In a typical scheme, if the colors are red, green, and blue, red and blue represent 0 and 1 in a Boolean circuit, while green is the "control" color.   As a final step, all of the precolored vertices are identified together into a complete graph on 3 vertices (a triangle) which is called the palette.   The three colors of the palette are arbitrary and are logically called "red", "green", and "blue"; and then coloring the rest of the graph can be equivalent to any coloring extension problem.  It is not hard to generalize this to $k$-coloring with larger $k$:  You have a larger palette, and you can force all of the uncolored vertices of the graph to be (notional) red, green, and blue and not really use the other colors.
Circuit satisfiability is easily NP-hard for circuits with bounded valence.  The valence is automatically bounded except for fanout, and you can make the fanout at most 2 locally with a cheap step such as inserting NOT gates between partial fanouts.   So, the only remaining issue is that the valence is very high at the palette itself.  It is not hard to replicate the palette with a bounded-valence gadget and then spread out the use of the palette across many copies.
Of course, as John Machacek points out, if you have a sufficiently severe bound on valence, then a coloring must exist or can be found in polynomial time, e.g., by the greedy algorithm in the baby Brooks theorem.  (The baby Brooks theorem say that the chromatic number is at most the max valence plus 1; the more serious theorem reduces the upper bound by 1 except in the case of a complete graph or an odd cycle.) 
A: If we consider very sparse graphs to be subcubic graphs (i.e. graphs with maximum degree at most 3) as suggested in the comments, the answer is that vertex coloring is never hard. Coloring of subcubic graphs can be done in polynomial time.
Let $G$ be a  connected subcubic graph. By Brooks' Theorem the graph $G$ is $3$-colorable unless $G = K_4$. Moreover, it is easy (for any graph) to decide if it is $1$-colorable or $2$-colorable. This shows the decision problem is easy for subcubic graphs. Actually producing a coloring can also be done efficiciently.  For example, one can the algorithm in $\Delta$-list vertex coloring in linear time by Skulrattanakulchai.
