Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search?
First of all keep in mind that this is just an analogy meant to convey the intuition behind the DFS algorithm on graphs.
Now graphs can be directed, which would correspond to having a labyrinth with junctions/rooms and one-way pathways between them.
Then it is possible for you to be in some room $r_0$ and to travel to some other room $r_1 \neq r_0$ as a part of your labyrinth exploration.
Maybe all paths from $r_1$ lead to a dead end, so you backtrack to $r_0$. From there you continue to explore until you reach a third room $r_2 \not\in \{r_0, r_1\}$.
The problem arises if $r_2$ has a pathway to $r_1$: without any record that you already visited $r_1$, you'd visit it again.
To stick with your analogy, you don't need strings if the floor plan of your labyrinth can be represented as a tree (rather than a general graph). Indeed, if you have a tree and some (arbitrary) order among the edges from a vertex to their children (as it is usually the case in actual implementations), you can implement a DFS without keeping any information other than the current and previous vertices of the search (i.e., an edge of the tree).