NP-hard problems but only for n≥3

• 2-SAT is in P; 3-SAT is NP-complete.

• Exact cover by 2-sets is in P; exact cover by 3-sets is NP-complete

• Two-dimensional matching is in P; three-dimensional matching is NP-complete

• Graph 2-coloring is trivially in P; graph 3-coloring is NP-complete

Are there other well-known or important examples that are similar, in that there is a family of problems with a natural parameter $n$, where the problem is known to be in P when $n<3$ and known to be NP-hard when $n≥3$?

In graph coloring you are looking for a partitioning of the vertex set into independent sets. Now, there are many arguably well-known similarly behaving (i.e., easy for $k=2$, hard for $k \geq 3$) problems where instead you want to find a partition into $k$ sets which could be (i) independent dominating, (ii) dominating, (iii) total nearly perfect, (iv) weakly perfect dominating, or (v) total perfect dominating, to name a few. Many of these problems also appear under different shorter names like "domatic number", "total domatic number", and so on. For more details, see e.g., the work of Heggernes and Telle [1, Table 1] (there's quite a bit of follow-up work as well).

Also, graph coloring is naturally linked to the classical and heavily-studied chromatic index (i.e., edge coloring) via the line graph. Further, deciding if a $k$-regular graph can be edge $k$-colored properly is NPC for every $k \geq 3$.

[1] Heggernes, Pinar, and Jan Arne Telle. "Partitioning graphs into generalized dominating sets." Nord. J. Comput. 5.2 (1998): 128-142.

StackExchange Computer Science Q#117141, answer score: 5