doi:10.1109/IRC.2017.42 We propose a multi-legged robot that has legs in all directions around its roll axis. The design realizes the robot to move towards the same direction even if it rolls over. Our target is to make a small sized robot so that it is able to move in narrow areas. In our design, all the legs are driven by a single worm gear placed along with the roll axis. Each leg performs strides by using a simple slider-crank mechanism driven by a spur gear attached on the worm gear. In this case, a walking gait such as a tripod gait is realized by settling appropriate initial phases of legs. The robot has to perform a stable gait at any rotation positions along the roll axis. In any rotation position, two rows of legs are used for a gait to support and drive the body. This means that every leg is shared by two different gaits. To find an initial phase for a given number of legs, we use a method of solving a graph coloring problem by assigning a phase of a leg as a color of a node and the relationships of geographical adjacency of two legs as a link. This allocates stance legs spatially uniformly over the side face of the robot, which gives stability of the gait. We made prototypes of robots that have 9 legs (each 3 legs allocated on 3 directions) and 12 legs (each 3 legs allocated on 4 directions). We conducted running tests under hard and soft surfaces. The results showed that the proposing design method is able to realize a compact and a roll-free legged robot.