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? 



Sparse graphs that are hard to color
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](https://en.wikipedia.org/wiki/Brooks%27_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](http://www.sciencedirect.com/science/article/pii/S0020019005003558) by Skulrattanakulchai.


