The border between P and NP for some problems
Approximation algorithms are most often encountered in the context of optimization problems. Consider the problem of minimizing some function $f$ subject to constraints $C$. An $\alpha$ approximation algorithm (where $\alpha$ can depend on some parameters of the instance, such as the number of vertices in a graph) is a (usually) polynomial time algorithm which produces a feasible solution (that is, one satisfying the constraints $C$) whose value is at most $\alpha$ times the optimum.

In some cases, bicriteria approximation algorithms are considered. These are algorithms as above, with the only difference being that the solution doesn't satisfy the constraints $C$ but rather some weaker version of them $C'$. See this question for some examples.

In the case of 3-coloring, your notion is very similar to the following optimization version of 3-coloring: given a graph, find a 3-coloring which violates the least number of constraints. There are several hardness results that show that it is difficult to approximate the optimum, even if you are allowed to use more colors (in the spirit of bicriteria optimization problems). For example, Guruswami and Khanna, in their paper On the hardness of 4-coloring a 3-colorable graph, show that it is NP-hard to distinguish between the following two classes of graphs: (i) 3-colorable graphs, (ii) graphs in which every 4-coloring has an $\epsilon_0$-fraction of monochromatic edges (for some constant $\epsilon_0$).

Similarly, your relaxation of the Hamiltonian path problem can be rephrased as an optimization problem: the longest path problem. It is NP-hard for any constant $k$, and even for much larger $k$; see the paper mentioned in Wikipedia, On approximating the longest path in a graph by Karger, Motwani and Ramkumar.